链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

链表在物理上不连续 在逻辑上连续

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环

在这么多链表结构中我们主要学习两种

1. 无头单向非循环链表：无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
2. 无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

实现无头单向非循环链表

public class SingleLinkedList {//头插法public void addFirst(int data){}//尾插法public void addLast(int data){}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data){}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){return false;}//删除第一次出现关键字为key的节点public void remove(int key){}//删除所有值为key的节点public void removeAllKey(int key){}//得到单链表的长度public int size(){return -1;}public void clear() {}public void display() {}
}

实现上面的接口即可

public class SingleLinkedList {//内部类 实现了一个节点static class ListNode {public int val;//节点的值public ListNode next;//节点中储存了下一个节点的地址public ListNode(int val) {this.val = val;}//初始化节点的构造方法}//永远指向头节点public ListNode head;//打印链表中所有节点的值public void show() {ListNode cur = head;//记录头节点的位置 遍历不改变头节点位置while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;//当cur不为空时 打印每个节点的val值 使cur指向下一个节点}System.out.println();}//头插法public void addFirst(int data) {ListNode node = new ListNode(data);//新建一个节点 将这个节点头插node.next = head;//将新节点指向头节点 成为新的头节点head = node;//head永远指向头节点 head也改为node}//尾插法public void addLast(int data) {ListNode node = new ListNode(data);//新建一个节点 将这个节点尾插if (head == null) {head = node;//如果此时链表为空 那么该节点就是新的头节点return;}ListNode cur = head;//记录头节点while (cur.next != null) {cur = cur.next;}//此时cur指向的就是最后一个节点//只需要把最后一个节点指向nodecur.next = node;}//任意位置插入,第一个数据节点为0号下标public void addIndex(int index, int data) {int len = size();//判断下标的合法性if (index < 0 || index > len) {throw new IndexOutOfBoundsExcption("在任意位置插入数据时，index位置不合法: " + index);}//如果插入位置时头位置 则是头插if (index == 0) {addFirst(data);}//如果插入位置时尾部 则是尾插if (index == len) {addLast(data);}}//查找是否包含关键字key是否在单链表当中public boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key) {if (head == null) {return;}//如果头节点是要移除的节点if (head.val == key) {head = head.next;return;}ListNode prev;}//查找目标节点的上一个节点private ListNode searchPrev(int key) {ListNode prev = head;while (prev.next != null) {if (prev.next.val == key) {return prev;} else {prev = prev.next;}}return null;}//删除所有值为key的节点public void removeAllKey(int key) {if (head != null) {return;}ListNode cur = head.next;ListNode prev = head;while (cur != null) {if (cur.val == key) {prev.next = cur.next;cur = cur.next;} else {prev = cur;cur = cur.next;}}if (head.val == key) {head = head.next;}}//得到单链表的长度public int size() {int count = 0;ListNode cur = head;//如果是引用类型用equals比较while (cur != null) {count++;cur = cur.next;}return count;}public void clear() {//this.head = null;while (head != null) {ListNode headNext = head.next;head.next = null;head = headNext;}}public void display() {ListNode cur = head;while (cur != null) {System.out.println(cur.val);cur = cur.next;}}
}

LinkedList 模拟实现

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

public class MyLinkedList {static class ListNode {public int val;public ListNode prev;//储存上一个节点的位置public ListNode next;//储存下一个节点的位置public ListNode(int val) {this.val = val;}}//获取双向链表的长度 和双向无关public ListNode head;public ListNode last;//获取链表的长度public int size() {int len = 0;ListNode cur = head;//遍历链表求长度while (cur != null) {len++;cur = cur.next;}return len;}//打印链表内容public void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val);cur = cur.next;}System.out.println();}//查找某个关键字key是否在链表中public boolean contains(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {return true;}cur = cur.next;}return false;}//头插public void addFirst(int data) {ListNode node = new ListNode(data);//如果链表为空 插入的同时初始化头节点和尾节点if (head == null) {head = node;last = node;return;}node.next = head;head.prev = node;head = node;}//尾插法public void addLast(int data) {ListNode node = new ListNode(data);if (head == null) {head = node;last = node;return;}node.prev = last;last.next = node;last = node;}public void addIndex(int index, int data) {int size = size();if (index < 0 || index > size) {throw new IndexOutOfBounds("双向链表index下标不合法：" + index);}if (index == 0) {addFirst(data);return;}if (index == size) {addLast(data);return;}ListNode cur = head;while (index != 0) {cur = cur.next;index--;}ListNode node = new ListNode(data);node.next = cur;cur.prev.next = node;node.prev = cur.prev;cur.prev = node;}public void remove(int key) {ListNode cur = head;while (cur != null) {if (cur.val == key) {//开始删除if (cur == head) {//如果是头节点 删除头节点head = head.next;//如果删除后还有节点if (head != null) {head.prev = null;} else {last = null;//此时head = head.next head已经为null//只需要将last也置为null即可}} else {cur.prev.next = cur.next;//将cur之前的节点next指向改为cur的下一个节点//判断cur是否为尾节点if (cur.next != null) {cur.next.prev = cur.prev;//将后面节点的prev指向cur的prev} else {last = cur.prev;//如果为最后一个节点 就把last向前移}}return;} else {cur = cur.next;}}}public void removeAllKey(int key){ListNode cur = head;//逻辑和删除一个元素一模一样while (cur != null) {if (cur.val == key) {//开始删除if (cur == head) {//如果是头节点 删除头节点head = head.next;//如果删除后还有节点if (head != null) {head.prev = null;} else {last = null;//此时head = head.next head已经为null//只需要将last也置为null即可}} else {cur.prev.next = cur.next;//将cur之前的节点next指向改为cur的下一个节点//判断cur是否为尾节点if (cur.next != null) {cur.next.prev = cur.prev;//将后面节点的prev指向cur的prev} else {last = cur.prev;//如果为最后一个节点 就把last向前移}}}cur = cur.next;}}public void clear(){ListNode cur = head;while (cur != null){ListNode curNext = cur.next;cur.prev = null;cur.next = null;cur = curNext;}head = null;last = null;}
}

ArrayList和LinkedList的区别