原文链接：wangwei.one/posts/java-…
链表
定义
逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。
由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL(空)）。这种结构成为 "单向链表"。
在单向链表的基础上，给各个结点额外配备一个指针变量，用于指向每个结点的直接前趋元素。这样的链表被称为“双向链表”或者“双链表”。
当单向链表的尾部数据指向头部数据时，就构成了单向循环链表。
当双向链表的头部和尾部相互指向时，就构成了双向循环链表。
单向链表
单向链表在插入元素、删除元素时，需要获取前驱元素，需要从head开始遍历，时间复杂度为O(n)。
根据index查询对应元素，也需要从head开始遍历，时间复杂度为O(n)。
代码实现
package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/*** Single Linked List** @author https://wangwei.one* @date /12/25*/public class SingleLinkedList<T> implements IList<T> {/*** size*/private int size = 0;/*** head node*/private Node<T> head;/*** tail node*/private Node<T> tail;/*** add element** @param element* @return*/@Overridepublic boolean add(T element) {return addLast(element);}/*** add element at index** @param index* @param element* @return*/@Overridepublic boolean add(int index, T element) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}if (index == size) {return add(element);} else {return addBefore(index, element);}}/*** Add Last element** @param element* @return*/private boolean addLast(T element) {Node<T> last = tail;Node<T> newNode = new Node<>(null, element);tail = newNode;// if linked list is emptyif (last == null) {head = newNode;} else {last.next = newNode;}size++;return true;}/*** add element before certain element** @param index* @param element* @return*/private boolean addBefore(int index, T element) {checkPositionIndex(index);// prev nodeNode<T> prev = null;Node<T> x = head;for (int i = 0; i < index; i++) {prev = x;x = x.next;}// current nodeNode<T> current = x;// new nodeNode<T> newNode = new Node<>(current, element);// if current node is headif (prev == null) {head = newNode;} else {prev.next = newNode;}size++;return true;}/*** remove element** @param element* @return*/@Overridepublic boolean remove(T element) {Node<T> prev = null;Node<T> x = head;if (element == null) {while (x != null && x.element != null) {prev = x;x = x.next;}} else {while (x != null && !x.element.equals(element)) {prev = x;x = x.next;}}// if this linked is null OR don't find elementif (x == null) {return false;}Node<T> next = x.next;// if delete node is headif (prev == null) {head = next;} else {prev.next = next;}// if delete node is tailif (next == null) {tail = prev;}// for GCx.element = null;x = null;size--;return true;}/*** remove element by index** @param index* @return*/@Overridepublic T remove(int index) {checkPositionIndex(index);Node<T> prev = null;Node<T> x = head;for (int i = 0; i < index; i++) {prev = x;x = x.next;}// if linked is emptyif (x == null) {return null;}Node<T> next = x.next;// if delete node is headif (prev == null) {head = next;} else {prev.next = next;}// if delete node is tailif (next == null) {tail = prev;}size--;return x.element;}/*** set element by index** @param index* @param element* @return old element*/@Overridepublic T set(int index, T element) {checkPositionIndex(index);Node<T> node = node(index);T oldElement = node.element;node.element = element;return oldElement;}/*** get element by index** @param index* @return*/@Overridepublic T get(int index) {Node<T> node = node(index);return node == null ? null : node.element;}/*** get element by index** @param index* @return*/private Node<T> node(int index) {checkPositionIndex(index);Node<T> x = head;for (int i = 0; i < index; i++) {x = x.next;}return x;}/*** check index** @param index*/private void checkPositionIndex(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}/*** clear list*/@Overridepublic void clear() {for (Node<T> x = head; x != null; ) {Node<T> next = x.next;x.element = null;x.next = null;x = next;}head = tail = null;size = 0;}/*** contain certain element** @param element*/@Overridepublic boolean contains(T element) {if (element == null) {for (Node<T> x = head; x != null; x = x.next) {if (x.element == null) {return true;}}} else {for (Node<T> x = head; x != null; x = x.next) {if (x.element.equals(element)) {return true;}}}return false;}/*** get list size** @return*/@Overridepublic int size() {return size;}/*** Linked List Node** @param <T>*/private class Node<T> {private Node<T> next;private T element;public Node(Node<T> next, T element) {this.next = next;this.element = element;}}}复制代码
源代码
双向链表
相比于单向链表，双向链表多了一个前驱指针，在查找前驱节点时，时间复杂度降低为了O(1)。
通过index查询，删除某个node节点，时间复杂度都降为了O(1)。代码如下：
代码实现
package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/*** Doubly Linked List** @param <T>* @author https://wangwei.one* @date /04/28*/public class DoublyLinkedList<T> implements IList<T> {/*** size*/private int size = 0;/*** head element*/private Node<T> head = null;/*** tail element*/private Node<T> tail = null;/*** add element** @param element* @return*/@Overridepublic boolean add(T element) {return addLast(element);}/*** add element at index** @param index* @param element* @return*/@Overridepublic boolean add(int index, T element) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}if (index == size) {return add(element);} else {return addBefore(element, node(index));}}/*** Add Last element** @param element* @return*/private boolean addLast(T element) {final Node<T> last = tail;Node<T> newNode = new Node<>(last, element, null);tail = newNode;if (last == null) {head = newNode;} else {last.next = newNode;}size++;return true;}/*** add element before certain element** @param element* @param target* @return*/private boolean addBefore(T element, Node<T> target) {Node<T> prev = target.prev;Node<T> newNode = new Node<>(prev, element, target);target.prev = newNode;if (prev == null) {head = newNode;} else {prev.next = newNode;}size++;return true;}/*** remove node by element** @param element* @return*/@Overridepublic boolean remove(T element) {if (element == null) {for (Node<T> x = head; x != null; x = x.next) {if (x.element == null) {unlink(x);return true;}}} else {for (Node<T> x = head; x != null; x = x.next) {if (element.equals(x.element)) {unlink(x);return true;}}}return false;}/*** remove node by index** @param index* @return*/@Overridepublic T remove(int index) {return unlink(node(index));}/*** get element by index** @param index* @return*/private Node<T> node(int index) {checkPositionIndex(index);if (index < (size >> 1)) {Node<T> x = head;for (int i = 0; i < index; i++) {x = x.next;}return x;} else {Node<T> x = tail;for (int i = size - 1; i > index; i--) {x = x.prev;}return x;}}/*** unlink node** @param node*/private T unlink(Node<T> node) {final T element = node.element;final Node<T> prev = node.prev;final Node<T> next = node.next;// if unlink is headif (prev == null) {head = next;} else {prev.next = next;// clear prevnode.prev = null;}// if unlink is tailif (next == null) {tail = prev;} else {next.prev = prev;node.next = null;}node.element = null;size--;return element;}private void checkPositionIndex(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}/*** set element by index** @param index* @param element* @return*/@Overridepublic T set(int index, T element) {checkPositionIndex(index);Node<T> oldNode = node(index);T oldElement = oldNode.element;oldNode.element = element;return oldElement;}/*** get element by index** @param index* @return*/@Overridepublic T get(int index) {Node<T> node = node(index);return node == null ? null : node.element;}/*** clear list*/@Overridepublic void clear() {for (Node<T> x = head; x != null; ) {Node<T> next = x.next;x.element = null;x.next = null;x.prev = null;x = next;}head = tail = null;size = 0;}/*** contain certain element** @param element*/@Overridepublic boolean contains(T element) {if (element == null) {for (Node<T> x = head; x != null; x = x.next) {if (x.element == null) {return true;}}} else {for (Node<T> x = head; x != null; x = x.next) {if (element.equals(x.element)) {return true;}}}return false;}/*** get list size** @return*/@Overridepublic int size() {return size;}/*** node** @param <T>*/private class Node<T> {private T element;private Node<T> prev;private Node<T> next;public Node(Node<T> prev, T element, Node<T> next) {this.element = element;this.prev = prev;this.next = next;}}}复制代码
源代码
单向循环链表
与单向链表一样，在寻找前驱节点时，需要遍历整个链表，时间复杂度为O(n).
在第一次添加元素时，特别注意，head与tail为同一节点，并且需要自指向。
package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/*** Singly Circular Linked List** @param <T>* @author https://wangwei.one* @date /05/03*/public class SinglyCircularLinkedList<T> implements IList<T> {/*** size*/private int size = 0;/*** head node*/private Node<T> head = null;/*** tail node*/private Node<T> tail = null;/*** add element** @param element* @return*/@Overridepublic boolean add(T element) {return addLast(element);}/*** add element at index** @param index* @param element* @return*/@Overridepublic boolean add(int index, T element) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}if (index == size) {return add(element);} else {return addBefore(index, element);}}/*** Add Last element** @param element* @return*/private boolean addLast(T element) {final Node<T> last = tail;Node<T> newElement = new Node<>(element, head);tail = newElement;if (last == null) {head = newElement;// we need linked itself when add an element firsttail.next = head;} else {last.next = newElement;}size++;return true;}/*** add element before certain element** @param element* @param element* @return*/private boolean addBefore(int index, T element) {checkPositionIndex(index);// prev node, start with tailNode<T> prev = tail;Node<T> x = head;for (int i = 0; i < index; i++) {prev = x;x = x.next;}// current nodeNode<T> current = x;// new nodeNode<T> newNode = new Node<>(element, current);if (index == 0) {head = newNode;}prev.next = newNode;size++;return true;}/*** remove node by element** @param element* @return*/@Overridepublic boolean remove(T element) {// start with tailNode<T> prev = tail;// start with headNode<T> x = head;// start with index -1int prevIndex = -1;for (int i = 0; i < size; i++) {if (element == null && x.element == null) {break;}if (element != null && element.equals(x.element)) {break;}prev = x;x = x.next;prevIndex = i;}// if this linked list is emptyif (x == null) {return false;}// if don't match elementif (prevIndex == size - 1) {return false;}Node<T> next = x.next;// if delete node is headif (prevIndex == -1) {head = next;}// if delete node is tailif (prevIndex == size - 2) {tail = prev;}prev.next = next;size--;if (size == 0) {head = tail = null;}// for GCx = null;return true;}/*** remove element by index** @param index* @return*/@Overridepublic T remove(int index) {checkPositionIndex(index);Node<T> prev = tail;Node<T> x = head;for (int i = 0; i < index; i++) {prev = x;x = x.next;}// if linked is emptyif (x == null) {return null;}Node<T> next = x.next;// if delete node is headif (index == 0) {head = next;}// if delete node is tailif (index == size - 1) {tail = prev;}prev.next = next;size--;if (size == 0) {head = tail = null;}return x.element;}/*** get element by index** @param index* @return*/private Node<T> node(int index) {checkPositionIndex(index);Node<T> x = head;for (int i = 0; i < index; i++) {x = x.next;}return x;}private void checkPositionIndex(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}/*** set element by index** @param index* @param element* @return*/@Overridepublic T set(int index, T element) {checkPositionIndex(index);Node<T> oldNode = node(index);T oldElement = oldNode.element;oldNode.element = element;return oldElement;}/*** get element by index** @param index* @return*/@Overridepublic T get(int index) {return node(index).element;}/*** clear list element*/@Overridepublic void clear() {for (Node<T> x = head; x != null; ) {Node<T> next = x.next;x.element = null;x.next = null;x = next;}head = tail = null;size = 0;}/*** contain certain element** @param element*/@Overridepublic boolean contains(T element) {if (head == null) {return false;}Node<T> x = head;for (int i = 0; i < size; i++) {if (element == null && x.element == null) {return true;}if (element != null && element.equals(x.element)) {return true;}x = x.next;}return false;}/*** get list size** @return*/@Overridepublic int size() {return size;}/*** Node** @param <T>*/private class Node<T> {private T element;private Node<T> next;public Node(T element, Node<T> next) {this.element = element;this.next = next;}}}复制代码
源代码
双向循环链表
双向循环链表相比单向循环链表，降低了查找前驱节点的复杂度，时间复杂度为O(1).
同样第一次添加元素时，head与tail为同一元素，需要自指向。
package one.wangwei.algorithms.datastructures.list.impl;import one.wangwei.algorithms.datastructures.list.IList;/*** Doubly circular linked list** @author https://wangwei.one* @date /12/21*/public class DoublyCircularLinkedList<T> implements IList<T> {/*** size*/private int size;/*** head node*/private Node<T> head;/*** tail node*/private Node<T> tail;/*** add element** @param element* @return*/@Overridepublic boolean add(T element) {return addLast(element);}/*** add element at index** @param index* @param element* @return*/@Overridepublic boolean add(int index, T element) {if (index < 0 || index > size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}if (index == size) {return add(element);} else {return addBefore(index, element);}}/*** Add last element** @param element* @return*/private boolean addLast(T element) {Node<T> last = tail;Node<T> newNode = new Node<>(element, last, head);tail = newNode;// add element at firstif (last == null) {head = newNode;tail.next = head;} else {last.next = newNode;}head.prev = tail;size++;return true;}/*** add element before certain element** @param index* @param element* @return*/private boolean addBefore(int index, T element) {Node<T> target = node(index);Node<T> prev = target.prev;Node<T> newNode = new Node<>(element, prev, target);prev.next = newNode;target.prev = newNode;if (index == 0) {head = newNode;}size++;return true;}/*** remove element** @param element* @return*/@Overridepublic boolean remove(T element) {// start with headNode<T> x = head;// start with index -1int prevIndex = -1;for (int i = 0; i < size; i++) {if (element == null && x.element == null) {break;}if (element != null && element.equals(x.element)) {break;}x = x.next;prevIndex = i;}// if this linked list is emptyif (x == null) {return false;}// if don't match elementif (prevIndex == size - 1) {return false;}Node<T> prev = x.prev;Node<T> next = x.next;// if delete node is headif (prevIndex == -1) {head = next;}// if delete node is tailif (prevIndex == size - 2) {tail = prev;}prev.next = next;next.prev = prev;size--;if (size == 0) {head = tail = null;}// for GCx = null;return true;}/*** remove element by index** @param index* @return*/@Overridepublic T remove(int index) {checkPositionIndex(index);Node<T> x = head;for (int i = 0; i < index; i++) {x = x.next;}// if linked is emptyif (x == null) {return null;}Node<T> prev = x.prev;Node<T> next = x.next;// if delete node is headif (index == 0) {head = next;}// if delete node is tailif (index == size - 1) {tail = prev;}prev.next = next;next.prev = prev;size--;if (size == 0) {head = tail = null;}return x.element;}private void checkPositionIndex(int index) {if (index < 0 || index >= size) {throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);}}/*** set element by index** @param index* @param element* @return old element*/@Overridepublic T set(int index, T element) {Node<T> oldNode = node(index);T oldElement = oldNode.element;oldNode.element = element;return oldElement;}/*** get element by index** @param index* @return*/@Overridepublic T get(int index) {return node(index).element;}/*** get element by index** @param index* @return*/private Node<T> node(int index) {checkPositionIndex(index);if (index < (size >> 1)) {Node<T> x = head;for (int i = 0; i < index; i++) {x = x.next;}return x;} else {Node<T> x = tail;for (int i = size - 1; i > index; i--) {x = x.prev;}return x;}}/*** clear list*/@Overridepublic void clear() {for (Node<T> x = head; x != null; ) {Node<T> next = x.next;x.element = null;x.next = null;x = next;}head = tail = null;size = 0;}/*** contain certain element** @param element* @return*/@Overridepublic boolean contains(T element) {if (head == null) {return false;}Node<T> x = head;for (int i = 0; i < size; i++) {if (element == null && x.element == null) {return true;}if (element != null && element.equals(x.element)) {return true;}x = x.next;}return false;}/*** get list size** @return*/@Overridepublic int size() {return size;}/*** Node** @param <T>*/private class Node<T> {private T element;private Node<T> prev;private Node<T> next;public Node(T element, Node<T> prev, Node<T> next) {this.element = element;this.prev = prev;this.next = next;}}}复制代码
源代码
