概念和图示
链表是一条有节点（Node）所组成链式数据结构，每个节点存储的元素（e）以及指向下一个元素的节点（next）：
image.png
使用类表示如下：
class Node {
E e;
Node next;
}
一条存储整型的链表如下：
image.png
通常来讲链表都会用一个头节点（head）来索引该链表。然而，一般为了增删改查等操作上的统一性，会添加一个虚拟头节点（dummyHead）:
image.png
实现
首先定义链表类和节点类，维护的变量和通用方法：
public class LinkedList<E> {
/**
* 维护一个虚拟头节点，以使对首节点的操作和其他操作一致
*/
private final Node dummyHead;
private int size;
private class Node {
E e;
Node next;
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}
}
public LinkedList() {
dummyHead = new Node();
}
public boolean isEmpty() {
return size == 0;
}
public int getSize() {
return size;
}
}
增
增加操作需要找到对应位置之前的节点(prevNode)，再把新增节点的next赋值为prevNode.next，再把prevNode.next赋值为新增节点。
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed, invalid index.");
}
Node prevNode = dummyHead;
for (int i = 0; i < index; i++) {
prevNode = prevNode.next;
}
prevNode.next = new Node(e, prevNode.next);
size++;
}
public void addFirst(E e) {
add(0, e);
}
public void addLast(E e) {
add(size, e);
}
删
删除操作也是需要找到对应位置之前的节点(prevNode)，再把prevNode.next指向待删节点deleteNode.next。
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed, invalid index.");
}
Node prevNode = dummyHead;
for (int i = 0; i < index; i++) {
prevNode = prevNode.next;
}
Node deleteNode = prevNode.next;
prevNode.next = deleteNode.next;
deleteNode.next = null;
size--;
return deleteNode.e;
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size - 1);
}
public void removeElement(E e) {
Node prevNode = dummyHead;
while (prevNode.next != null) {
if (prevNode.next.e.equals(e)) {
Node deleteNode = prevNode.next;
prevNode.next = deleteNode.next;
deleteNode.next = null;
size--;
}
}
}
改和查
修改和查找则可以找到对应位置，直接操作即可：
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed, invalid index.");
}
Node curNode = dummyHead;
for (int i = 0; i <= index; i++) {
curNode = dummyHead.next;
}
curNode.e = e;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed, invalid index.");
}
Node curNode = dummyHead;
for (int i = 0; i <= index; i++) {
curNode = dummyHead.next;
}
return curNode.e;
}
public E getFirst() {
return get(0);
}
public E getLast() {
return get(size - 1);
}
public boolean contains(E e) {
Node curNode = dummyHead.next;
while (curNode != null) {
if (curNode.e.equals(e)) {
return true;
}
curNode = curNode.next;
}
return false;
}
复杂度分析
对于链表来讲，由于每一次个操作都需要去遍历链表，因此每个操作都为O(n)。因此，链表通常不适合用于修改、删除和查找操作，通常只适用于在头节点增加和删除元素操作，因为在头节点处的复杂度都为O(1)。
链表栈
将链表头看成是栈顶，则可以依据链表实现一个栈：
public class LinkedListStack<E> implements Stack<E> {
private final LinkedList<E> list;
public LinkedListStack() {
list = new LinkedList<>();
}
@Override
public int size() {
return list.getSize();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void push(E e) {
list.addFirst(e);
}
@Override
public E pop() {
return list.removeFirst();
}
@Override
public E peek() {
return list.getFirst();
}
@Override
public String toString() {
return "LinkedListStack: top[ " +
list.toString() +
"]";
}
}
