链表链表 - 锐客网

【链表】链表通过指针将零散的数据块连接在一起，这些内存块被称为节点（Node）。通常每个节点除了储存数据之外还记录下一个节点的地址。

//Node类是LinkedList类的内部类，泛型E定义在LinkedList上 class Node { E e; //数据域 Node next; //下一个节点Node() { this(null, null); }Node(E e) { this(e, null); }Node(E e, Node next) { this.e = e; this.next = next; } }

与数组相比，数组的存储空间是连续的。因此为了保证数组的存储空间的连续性，需要搬移节点。而链表的各个节点是由指针串联起来的，插入和删除时只需维护指针即可，这样的时间复杂度为O(1)。
单链表LinkedList
设置虚拟头结点（哨兵）方便实现统一的逻辑代码，哨兵节点不存储数据。无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。下面是LinkedList的两个成员变量

private Node dummyHead; //哨兵 private int size; //构造器初始化 public LinkedList() { dummyHead = new Node(); size = 0; }

链表的重要操作

add(int index, E e):在index位置插入元素e

public viod add(int index, E e) { Node prev = dummyHead; //指针移动到目标节点的前一个节点上 for(int i = 0; i < index; i ++) { prev = prev.next; }//修改指针的指向 //Node newNode = new Node(e); //newNode.next = prev.next; //prev.next = newNode; //上面的三行合并成一行 prev.next = new Node(e, prev.next); size ++; }
removeElement(E e)：移除指定的元素e

public void removeElement(E e) { Node prev = dummyHead; while(prev.next != null) { if(prev.next.e.equals(e)) { //在找到目标元素的前一个节点处停止 break; } prev = prev.next; } if(prev.next != null) { prev.next = prev.next.next; } }
remove(int index)：移除指定位置上的元素，并返回该元素

public E remove(int index) { Node prev = dummyHead; //在找到目标元素的前一个节点处停止 for(int i = 0; i < index; i ++) { prev = prev.next; }//记录节点，用于返回 Node retNode = prev.next; //修改指针 prev.next = retNode.next; //销毁被删元素 retNode.next = null; size --; return retNode.e; }