一、什么是LinkedList？
LinkedList 的底层是双向链表结构 ( 链表后面介绍 ) ，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
在集合框架中， LinkedList 也实现了 List 接口，具体如下：
1. LinkedList 实现了 List接口
2. LinkedList 的底层使用了双向链表
3. LinkedList 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问
4. LinkedList 的任意位置插入和删除元素时效率比较高，时间复杂度为 O(1)
二、LinkedList的使用
构造方法：
| 方法 | 解释 |
LinkedList () |
无参构造 |
public LinkedList(Collection<? extends E> c) |
使用其他集合容器中元素构造 List |
public static void main(String[] args) { // 构造一个空的LinkedList List<Integer> list1 = new LinkedList<>(); List<String> list2 = new java.util.ArrayList<>(); list2.add("JavaSE"); list2.add("JavaWeb"); list2.add("JavaEE"); // 使用ArrayList构造LinkedList List<String> list3 = new LinkedList<>(list2); }
LinkedList的常用方法：
| 方法 | 解释 |
boolean add(E e) |
尾插e |
void add (int index, E element) |
将 e 插入到 index 位置 |
boolean addAll (Collection<? extends E> c) |
尾插 c 中的元素 |
E remove (int index) |
删除 index 位置元素 |
boolean remove (Object o) |
删除遇到的第一个 o |
E get (int index) |
获取下标 index 位置元素 |
E set (int index, E element) |
将下标 index 位置元素设置为 element |
void clear () |
清空 |
boolean contains (Object o) |
判断 o 是否在线性表中 |
int indexOf (Object o) |
返回第一个 o 所在下标 |
int lastIndexOf (Object o) |
返回最后一个 o 的下标 |
List<E> subList (int fromIndex, int toIndex) |
截取部分 list |
LinkedList的遍历：(foreach遍历、使用迭代器遍历---正向遍历、使用反向迭代器---反向遍历
LinkedList<String> list = new LinkedList<>(); list.add("javaSE"); list.add("javaWeb"); list.add("javaEE"); // foreach遍历 for (String x: list) { System.out.print(x + " "); } // 使用迭代器遍历---正向遍历 ListIterator<String> list1 = list.listIterator(); while (list1.hasNext()){ System.out.print(list1.next()+" "); } // 使用反向迭代器---反向遍历 ListIterator<String> lis2 = list.listIterator(list.size()); while (lis2.hasPrevious()){ System.out.print(lis2.previous()+" "); }
三、LinkedList自实现
public class MyLinkedList { static class ListNode{ int val; ListNode pre; ListNode next; public ListNode(int val){ this.val = val; } } public ListNode head;//头部 public ListNode tail;//尾部 public void addFirst(int data){ ListNode node = new ListNode(data); if (head == null){ head = node; tail = node; return; } node.next = head; head.pre = node; head = node; } public void addLast(int data){ ListNode node = new ListNode(data); if (head == null){ head = node; tail = node; return; } tail.next = node; node.pre = tail; tail = node; } //任意位置插入,第一个数据节点为0号下标 public boolean addIndex(int index,int data){ if (index < 0 || index > size()){ System.out.println("index位置不合法！"); return false; } if (index == 0){ addFirst(data); return true; } if (index == size()){ addLast(data); return true; } ListNode indexNode = findNode(index); ListNode node = new ListNode(data); node.pre = indexNode.pre; indexNode.pre.next = node; node.next = indexNode; indexNode.pre = node; return true; } public ListNode findNode(int index){ ListNode cur = head; while (index != 0){ cur = cur.next; index--; } return cur; } public boolean contains(int key){ ListNode cur = head; while (cur != null){ if (cur.val == key)return true; cur = cur.next; } return false; } 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.pre = null; } else { tail = null; } } else { cur.pre.next = cur.next; if (cur.next != null) { cur.next.pre = cur.pre; } else { tail = tail.pre; } } return; } 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.pre = null; } else { tail = null; } } else { cur.pre.next = cur.next; if (cur.next != null) { cur.next.pre = cur.pre; } else { tail = tail.pre; } } } cur = cur.next; } } public int size(){ ListNode cur = head; int count = 0; while (cur != null){ count++; cur = cur.next; } return count; } public void display(){ ListNode cur = head; while (cur != null){ System.out.print(cur.val + " "); cur = cur.next; } } public void clear(){ ListNode cur = head; while (cur != null){ ListNode temp = cur.next; cur.next = null; cur.pre = null; cur = temp; } head = null; tail = null; } }
四、链表实现逆序打印的两种方式（递归和非递归）
递归逆序打印：
public void display(ListNode head) { if(head == null) { return; } if(head.next == null) { System.out.print(head.val+" "); return; } display(head.next); System.out.print(head.val+" "); }
非递归逆序打印（用栈实现）：
public void display(ListNode head) { if (head == null) { return; } Stack<ListNode> stack = new Stack<>(); ListNode cur = head; while (cur != null) { stack.push(cur); cur = cur.next; } while (!stack.empty()) { ListNode ret = stack.pop(); System.out.print(ret.val+" "); } }
五、ArrayList和LinkedList有什么区别？
ArrayList实质是顺序表，底层是一个数组。LinkedList实质是一个链表。
他们都具有增删查改的功能，但是在实现方式上有区别。比如在插入元素的时候，ArrayList往0位置上插入一个元素，就需把整个数组整体往后移动，时间复杂度为O(N)。而LinkedList只需要修改指向就可以了，时间复杂度为O(1)。但是ArrayList可以支持随机访问，时间复杂度为O(1)，所以一般情况下ArrayList顺序表适合频繁根据下标位置访问，LinkedList比较适合插入和删除比较频繁的情况。
从存储上来说，ArrayList顺序表在物理上和逻辑上都是连续的，但是在扩容的时候，可能会造成空间的浪费。而LinkedList在物理上不一定是连续的，在逻辑上是连续的，可以做到随用随取。
| 不同点 | ArrayList | LinkedList |
存储空间上 |
物理上逻辑上一定连续 |
逻辑上连续，但物理上不一定连续 |
随机访问 |
支持 O(1) |
不支持： O(N) |
头插 |
需要搬移元素，效率低 O(N) |
只需修改引用的指向，时间复杂度为 O(1) |
插入 |
空间不够时需要扩容 |
没有容量的概念 |
应用场景 |
元素高效存储 + 频繁访问 |
任意位置插入和删除频繁 |
