数据结构与算法【链表：一】Java实现

目录

链表

单向链表

哨兵链表

双向链表

环形链表

---

链表

链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。

随机访问性能

根据 index 查找，时间复杂度 O(n)

插入或删除性能

• 起始位置：O(1)
• 结束位置：如果已知 tail 尾节点是 O(1)[双向链表]，不知道 tail 尾节点是 O(n)
• 中间位置：根据 index 查找时间 + O(1)

单向链表

单向链表中每个元素只知道下一个节点位置

单向链表的简单实现

public class SinglyLinkList implements Iterable<Integer> {private Node head = null;//节点类private static class Node {int value;Node next;public Node(int value, Node next) {this.value = value;this.next = next;}}//提供链表方法public void addFirst(int value) {head = new Node(value, head);}//向链表尾部添加节点public void addLast(int value) {Node last = findLast();if (last == null) {addFirst(value);}last.next = new Node(value, null);}private Node findLast() {if (head.next == null) {return null;}Node p = head;while (p.next != null) {p = p.next;}return p;}//遍历链表public void loop(Consumer<Integer> consumer) {Node pointer = head;while (pointer != null) {consumer.accept(pointer.value);pointer = pointer.next;}}@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node pointer = head;@Overridepublic boolean hasNext() {return pointer != null;}@Overridepublic Integer next() {int value = pointer.value;pointer = pointer.next;return value;}};}// 根据索引查找节点值private Node findByIndex(int index) {int i = 0;for (Node p = head; p != null; p = p.next, i++) {if (index == i) {return p;}}return null;}public int get(int index) {Node node = findByIndex(index);if (node == null) {throw new IllegalArgumentException("索引超出范围");}return node.value;}//插入元素public void insert(int index, int value) {if (index == 0) {addFirst(value);return;}//查找索引的上一个节点Node node = findByIndex(index - 1);if (node == null) {throw new IllegalArgumentException("索引超出范围");}node.next = new Node(value, node.next);}//移除首节点public void removeFirst() {if (head==null){throw new RuntimeException("链表为空。无法移除");}head = head.next;}//删除指定节点public void remove(int index){if (index==0){removeFirst();}//找到要删除的节点的前驱节点Node node = findByIndex(index - 1);Node remove = node.next;if (remove==null){//要删除的节点位置为空throw new IllegalArgumentException("索引越界");}node.next = remove.next;}
}

这种实现方法有一个弊端，那就是每次添加或是删除元素时都需要进行判断链表是否为空。因此提出了哨兵链表的概念

哨兵链表

所谓哨兵列表，就是头节点不存储数据，只为简化边缘判断使用。

具体代码如下

public class SinglyLinkListSentinel implements Iterable<Integer> {//头节点指向哨兵节点。值可以随便给private Node head = new Node(723468, null);//节点类private static class Node {int value;Node next;public Node(int value, Node next) {this.value = value;this.next = next;}}public void addFirst(int value) {//在链表头部添加节点时，应该在哨兵之后。insert(0, value);}//向链表尾部添加节点public void addLast(int value) {Node last = findLast();last.next = new Node(value, null);}private Node findLast() {Node p = head;while (p.next != null) {p = p.next;}return p;}//遍历链表public void loop(Consumer<Integer> consumer) {//从哨兵节点之后的节点开始遍历Node pointer = head.next;while (pointer != null) {consumer.accept(pointer.value);pointer = pointer.next;}}@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node pointer = head.next;@Overridepublic boolean hasNext() {return pointer != null;}@Overridepublic Integer next() {int value = pointer.value;pointer = pointer.next;return value;}};}// 根据索引查找节点值private Node findByIndex(int index) {//这里设置为-1是排除哨兵节点带来的影响int i = -1;for (Node p = head; p != null; p = p.next, i++) {if (index == i) {return p;}}return null;}public int get(int index) {Node node = findByIndex(index);if (node == null) {throw new IllegalArgumentException("索引超出范围");}return node.value;}//插入元素public void insert(int index, int value) {//查找索引的上一个节点Node node = findByIndex(index - 1);if (node == null) {throw new IllegalArgumentException("索引超出范围");}node.next = new Node(value, node.next);}//移除首节点public void removeFirst() {remove(0);}//删除指定节点public void remove(int index) {//找到要删除的节点的前驱节点Node node = findByIndex(index - 1);Node remove = node.next;if (remove == null) {//要删除的节点位置为空throw new IllegalArgumentException("索引越界");}node.next = remove.next;}
}

双向链表

每个元素知道上一个元素与下一个元素的地址

简单实现如下

public class DoublyLinkedListSentinel implements Iterable<Integer>{//头哨兵private Node head = new Node(null, null, 0);//尾哨兵private Node tail = new Node(null, null, 0);public DoublyLinkedListSentinel() {//初始化时，对头尾哨兵进行指定head.next = tail;tail.prev = head;}private static class Node {Node prev;Node next;int value;public Node(Node prev, Node next, int value) {this.prev = prev;this.next = next;this.value = value;}}//提供双向链表方法public Node findByIndex(int index) {int i = -1;for (Node p = head; p != tail; p = p.next, i++) {if (index == i) {return p;}}return null;}//插入首元素public void addFirst(int value) {insert(0, value);}//插入元素public void insert(int index, int value) {Node prev = findByIndex(index - 1);if (prev == null) {throw new RuntimeException("下标越界");}Node next = prev.next;Node node = new Node(prev, next, value);prev.next = node;next.prev = node;}//向尾节点添加public void addLast(int value){Node prev = tail.prev;Node addNode = new Node(prev, tail, value);prev.next = addNode;tail.prev = addNode;}//删除首节点public void removeFirst(){if (head.next==tail){throw new RuntimeException("链表为空");}Node remove = head.next;Node next = remove.next;head.next = next;next.prev = head;}//删除元素public void remove(int index) {Node prev = findByIndex(index - 1);if (prev == null) {throw new RuntimeException("下标越界");}Node remove = prev.next;Node next = remove.next;if (remove==tail){throw new RuntimeException("下标越界");}prev.next = next;next.prev = prev;}//获取元素public int get(int index){Node node = findByIndex(index);return node.value;}//遍历元素public void loop(Consumer<Integer> consumer) {Node pointer = head.next;while (pointer != tail) {consumer.accept(pointer.value);pointer = pointer.next;}}//迭代器实现@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p =head.next;@Overridepublic boolean hasNext() {return p!=tail;}@Overridepublic Integer next() {int value = p.value;p = p.next;return value;}};}
}

环形链表

环形链表的尾节点指向的是头节点head

环形链表我们也可以引入哨兵，空链表时，哨兵既做头节点也做尾节点。

简单实现代码如下

public class DoublyLinkedListSentinelTo implements Iterable<Integer> {private Node sentinel = new Node(null, null, -1);public DoublyLinkedListSentinelTo() {sentinel.prev = sentinel;sentinel.next = sentinel;}@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = sentinel.next;@Overridepublic boolean hasNext() {return p != sentinel;}@Overridepublic Integer next() {int value = p.value;p = p.next;return value;}};}private static class Node {Node prev;Node next;int value;public Node(Node prev, Node next, int value) {this.prev = prev;this.next = next;this.value = value;}}//提供循环链表的方法public Node findByIndex(int index) {int i = 0;for (Node p = sentinel.next; p != sentinel; i++, p = p.next) {if (index == i) {return p;}}return null;}public void addFirst(int value) {Node next = sentinel.next;Node addNode = new Node(sentinel, next, value);sentinel.next = addNode;next.prev = addNode;}public void insert(int index, int value) {if (index == 0) {addFirst(value);}Node prev = findByIndex(index - 1);if (prev == null) {throw new RuntimeException("下标越界");}Node next = prev.next;Node insertNode = new Node(prev, next, value);next.prev = insertNode;prev.next = insertNode;}public void addLast(int value) {Node prev = sentinel.prev;Node addNode = new Node(prev, sentinel, value);prev.next = addNode;sentinel.prev = addNode;}//删除第一个节点public void removeFirst() {Node remove = sentinel.next;if (remove == sentinel) {throw new RuntimeException("下标越界");}Node next = remove.next;sentinel.next = next;next.prev = sentinel;}//删除最后一个节点public void removeLast() {Node remove = sentinel.prev;if (remove == sentinel) {throw new RuntimeException("下标越界");}Node prev = remove.prev;prev.next = sentinel;sentinel.prev = prev;}//删除指定删除节点public void remove(int index) {if (index == 0) {removeFirst();}Node prev = findByIndex(index - 1);Node remove = prev.next;if (remove == sentinel) {throw new RuntimeException("下标越界");}Node next = remove.next;prev.next = next;next.prev = prev;}//遍历节点public void loop(Consumer<Integer> consumer) {for (Node p = sentinel.next; p != sentinel; p = p.next) {consumer.accept(p.value);}}
}