如何实现链表这种数据结构
零 特征说明
我们前面实现的动态数组、栈、队列，虽然说是动态数据结构，其实，其底层是依赖一个resize()方法来实现的。
而，链表其本质上是一个真正的动态数据结构。如同火车头挂接一节一节的车厢一样。
另外，跟数组比较起来，数组要求在内存中分配的内存空间必须是连续的，而链表则不需要连续的内存空间。正式由于这个原因，对于数组查找第n个元素可以直接使用下标来寻找，而链表则不能支持根据索引下标来随机访问。
一 实现思路
链表通过一个”结点”的数据结构来实现，每个结点中存放具体元素+指向下一个结点的指针。当某个结点的下一个指针为NULL时，则该结点是最后1个元素，也就意味着链表到此结束了。
另外，在链表中开辟一个头指针，它是结点这种数据类型的，用于指向链表中的第1个元素。
开辟一个整型变量size，用于记录链表中当前有多少个元素。
二代码实现
1 实现LinkedList类及其内部类Node
public class LinkedList<E>{
//实现链表的结点元素的内部类
private class Node{
//结点中存放的元素
public E e;
//指向下一个结点的指针
public Node next;
//constructor
public Node(E e,Node next){
this.e=e;
this.next=next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
@Override
public String toString(){
return e.toString();
}
}
//指向链表中的第一个元素
private Node head;
//记录链表中有多少个元素
private int size;
//constructor
public LinkedList(){
//链表中第1个元素为空
head=null;
size=0;
}
//查看链表元素个数
public int getSize(){
return size;
}
//链表是否为空
public boolean isEmpty(){
return size == 0;
}
}这样，我们动手实现了1个链表的基本框架：内部类Node用于表示每个结点，包含元素值和指向下一个结点的指针；链表中指向第1个结点的指针；记录链表中元素(结点)的个数的成员变量size；
2 实现向链表中插入元素的方法
//链表头部添加元素
public void addFirst(E e) {
Node node = new Node(e);
//先将新结点的下一个元素指向head.next，即链表头结点，这样就相当于在头部添加元素
node.next = head;
//然后，让head指向这个结点，进而这个新加的元素就成了第1个元素
head = node;
size++;
}
//在第i个位置处插入元素
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Illegal index");
}
if (index == 0) {
addFirst(e);
return;
}
Node node = new Node(e);
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
node.next = prev.next;
prev.next = node;
size++;
}
//在最后位置处添加元素
public void addLast(E e) {
add(size,e);
}3 带头结点的链表插入
前面，我们实现的链表，由于在链表任意位置插入元素时，需要特殊判断，插入位置是否在链表头，略微麻烦。于是，我们想到给链表设置一个虚拟头结点，让其指向链表的第1个结点。
public class LinkedList<E> {
private class Node{
public E e;
public 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);
}
@Override
public String toString() {
return e.toString();
}
}
//此处构建1个虚拟头结点
private Node dummyHead;
private int size;
public LinkedList() {
//构造链表时，虚拟头结点的元素为空，指向的下一个结点(链表中真正的第1个结点)也为空
dummyHead =new Node(null,null);
size = 0;
}
//查看链表中有多少元素
public int getSize() {
return size;
}
//链表是否为空
public boolean isEmpty() {
return size == 0;
}
//链表头部添加元素
public void addFirst(E e) {
add(0, e);
}
//在第i个位置处插入元素
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Illegal index");
}
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
size++;
}
//在最后位置处添加元素
public void addLast(E e) {
add(size,e);
}
}4 获取第index位置处的元素
//查找链表第index位置处元素，练习用
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed.Illegal index");
}
Node curr = dummyHead.next;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
return curr.e;
}
//查找第1个元素
public E getFirst() {
return get(0);
}
//查找最后1个元素
public E getLast() {
return get(size - 1);
}5 修改第index位置处元素为e
//修改第index位置处元素为e
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed.Illegal index");
}
Node curr = dummyHead.next;
for (int i = 0; i < index; i++) {
curr = curr.next;
}
curr.e = e;
}6 判断是否存在元素e
//判断是否存在元素e
public boolean contains(E e) {
Node curr = dummyHead.next;
//两种实现方式，for loop和while loop
// for (int i = 0; i < size; i++) {
// if (curr.e.equals(e)) {
// return true;
// }
// curr = curr.next;
// }
while (curr != null) {
if (curr.e.equals(e)) {
return true;
}
curr = curr.next;
}
return false;
}7 复写Object类的toString()
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(String.format("LinkedList:size %d\n", size));
Node curr = dummyHead.next;
for (int i = 0; i < size; i++) {
stringBuilder.append(curr);
curr = curr.next;
if (i != size - 1) {
stringBuilder.append("->");
}
}
return stringBuilder.toString();
}8 删除第index位置处元素并返回
//删除第index位置处元素
public E remove(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Delete failed.Illegal index");
}
Node pre = dummyHead;
//pre是待删除元素的前1个
for (int i = 0; i < index; i++) {
pre = pre.next;
}
//retNode存放但删除元素并返回
Node retNode = pre.next;
//pre的下一个元素指向待删除元素的next，从而删除了retNode这个待删除元素
pre.next = retNode.next;
//retNode.next=null，相当于retNode和我们的链表解除了关系
size--;
return retNode.e;
}
//删除第1个元素并返回
public E removeFirst() {
return remove(0);
}
//删除最后1个元素并返回
public E removeLast() {
return remove(size - 1);
}9 测试所有方法
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 10; i++) {
linkedList.add(i,i);
}
System.out.println(linkedList);
System.out.println("contains(8)：？"+linkedList.contains(8));
linkedList.set(5, 55);
System.out.println("remove(3): "+linkedList.remove(3));
System.out.println("after set(5,55):");
System.out.println(linkedList);
System.out.println("get(1)： "+linkedList.get(1));
System.out.println("getFirst()： "+linkedList.getFirst());
System.out.println("getLast()： "+linkedList.getLast());
System.out.println("removeFirst():"+linkedList.removeFirst());
System.out.println("removeLast():"+linkedList.removeLast());
System.out.println(linkedList);
}
//结果
LinkedList:size 10
0->1->2->3->4->5->6->7->8->9
contains(8)：？true
remove(3): 3
after set(5,55):
LinkedList:size 9
0->1->2->4->55->6->7->8->9
get(1)： 1
getFirst()： 0
getLast()： 9
removeFirst():0
removeLast():9
LinkedList:size 7
1->2->4->55->6->7->810 复杂度分析
添加：addLast(E e) O(n)；add(int index,E e) O(n); addFirst(E e) O(1);
删除：removeLast() O(n); remove(int index) O(n); removeFirst() O(1);
修改：set(int index,E e) O(n);
查找：contains(E e) O(n); getFirst() O(1);get(int index) O(n);getLast() O(n);
因此，我们可以得出实现的这种链表，其增删改查的时间复杂度都是O(n)。可是，我们为什么还要使用链表这种数据结构呢，它有什么用处呢？当我们指在链表头执行增删改查时，其时间复杂度瞬间降低到O(1)。结合栈这种数据结构，栈的操作都在栈顶位置，当我们用链表头来充当栈顶位置时，所有对于栈的操作：入栈、出栈、查看栈顶元素，我们就可以直接使用链表的链表头添加元素addFirst()/删除元素removeFirst()/getFirst()了，且时间复杂度都是O(1)。
三 小结
关于链表的实现，有2个比较麻烦的地方，就是头指针和引入虚拟头结点。引入虚拟头结点的目的主要是为了实现在链表头插入新结点/删除头结点的操作方便。引入的虚拟头结点都是指向链表中第一个真正的结点，这样链表中的所有结点都有了1个前驱结点。
一旦接受并理解了虚拟头结点，实现和使用链表就比较轻松一些了。引入虚拟头结点之后，所有对于链表的增、删、改、查，就都相当于对数组的操作了，结点下标从0开始，所有对于第index个位置处的增删改查，代码中的索引上限都是index，跟遍历数组是一样的思路。只不过呢，对于链表的增加和删除操作中，临时变量Node pre都是直接指向dummyHead，我们引入虚拟头结点的目的就是为了便于对链表头的插入和删除嘛。查找或修改第index个位置处的元素，我们都是把临时变量Node curr指向dummyHead.next。
