什么是LinkedList

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

说明：

1. LinkedList实现了List接口
2. LinkedList的底层使用了双向链表
3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5. LinkedList比较适合任意位置插入的场景

LinkedList的模拟实现

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

public class MyLinkedList implements IList{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;@Overridepublic void addFirst(int data) {}@Overridepublic void addLast(int data) {}@Overridepublic void addIndex(int index, int data) {}@Overridepublic boolean contains(int key) {return false;}@Overridepublic void remove(int key) {}@Overridepublic void removeAllKey(int key) {}@Overridepublic int size() {return 0;}@Overridepublic void clear() {}@Overridepublic void display() {}}

我们先来实现打印链表和得到链表长度

@Override
public int size() {ListNode cur = this.head;int count = 0;while(cur != null){cur = cur.next;count++;}return count;
}
@Override
public void display() {ListNode cur = this.head;while(cur != null){System.out.print(cur.val + " ");cur = cur.next;}System.out.println();
}

接下来实现头插法

@Override
public void addFirst(int data) {ListNode newNode = new ListNode(data);if(this.head == null){head = last = newNode;return;}head.prev = newNode;newNode.next = head;head = newNode;
}

public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addFirst(56);list.addFirst(45);list.addFirst(34);list.addFirst(23);list.addFirst(12);list.display();list.addFirst(33);list.display();System.out.println(list.size());}//结果为：//12 23 34 45 56 //33 12 23 34 45 56 //6
}

实现尾插法

@Override
public void addLast(int data) {ListNode newNode = new ListNode(data);if(head == null){head = last = newNode;return;}last.next = newNode;newNode.prev = last;;last = newNode;
}

public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(12);list.addLast(23);list.addLast(34);list.addLast(45);list.addLast(56);list.display();}//结果为：//12 23 34 45 56
}

实现任意位置插入,第一个数据节点为0号下标

private ListNode findIndex(int index){ListNode cur = this.head;while(index != 0){cur = cur.next;index--;}return cur;
}
@Override
public void addIndex(int index, int data) {int len = size();if(index < 0 || index > len - 1){return;}if(index == 0){addFirst(data);return;}if(index == len - 1){addLast(data);return;}ListNode cur = findIndex(index);ListNode newNode = new ListNode(data);newNode.next = cur;cur.prev.next = newNode;newNode.prev = cur.prev;cur.prev = newNode;
}

public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(12);list.addLast(23);list.addLast(34);list.addLast(45);list.addLast(56);list.display();list.addIndex(2,33);list.display();list.addIndex(0,33);list.display();list.addIndex(6,33);list.display();list.addIndex(8,33);list.display();}//结果为：//12 23 34 45 56//12 23 33 34 45 56//33 12 23 33 34 45 56//33 12 23 33 34 45 56 33//33 12 23 33 34 45 56 33
}

实现删除第一次出现关键字为key的节点

@Override
public void remove(int key) {ListNode cur = this.head;while(cur != null){if(cur.val == key){if(cur == this.head){head = head.next;if(head != null){head.prev = null;}}else{cur.prev.next = cur.next;if(cur.next == null){last = last.prev;}else{cur.next.prev = cur.prev;}}return;}cur = cur.next;}
}

public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(12);list.addLast(23);list.addLast(34);list.addLast(45);list.addLast(56);list.display();list.remove(12);list.display();list.remove(56);list.display();list.remove(34);list.display();}//结果为：//12 23 34 45 56//23 34 45 56//23 34 45//23 45
}

删除所有值为key的节点，我们只需要在删除第一次出现关键字为key的节点的代码上将return删除掉，让其循环到链表结尾

@Override
public void removeAllKey(int key) {ListNode cur = this.head;while(cur != null){if(cur.val == key){if(cur == this.head){head = head.next;if(head != null){head.prev = null;}}else{cur.prev.next = cur.next;if(cur.next == null){last = last.prev;}else{cur.next.prev = cur.prev;}}}cur = cur.next;}
}

public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(23);list.addLast(33);list.addLast(34);list.addLast(23);list.addLast(23);list.display();list.removeAllKey(23);list.display();}//结果为：//23 33 34 23 23//33 34
}

实现查找是否包含关键字key是否在双向链表当中，我们只需要遍历链表，找到返回true，没找到返回false

@Override
public boolean contains(int key) {ListNode cur = this.head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;
}

public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(12);list.addLast(23);list.addLast(34);list.addLast(45);list.addLast(56);list.display();System.out.println(list.contains(34));System.out.println(list.contains(100));}//结果为：//12 23 34 45 56//true//false
}

接下来实现clear，我们可以直接暴力的将head和last置为null
但是最后是将每个结点的prev和last都置为null，我们需要一个curN保留下一个结点，最后还需要将head和last置为null

@Override
public void clear() {ListNode cur = this.head;while(cur != null){ListNode curN = cur.next;cur.prev = null;cur.next = null;cur = curN;}this.head = this.last = null;
}

public class Test {public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.addLast(12);list.addLast(23);list.addLast(34);list.addLast(45);list.addLast(56);list.display();list.clear();list.display();}//结果为：//12 23 34 45 56//
}

LinkedList的使用

1. LinkedList的构造

方法	解释
LinkedList ()	无参构造
LinkedList (Collection<? extends E> c)	利用其他集合容器中元素构造List

import java.util.ArrayList;
import java.util.LinkedList;
public class Test {public static void main(String[] args) {//构造一个空的LinkedListLinkedList<Integer> list1 = new LinkedList<>();list1.add(1);list1.add(2);list1.add(3);list1.add(4);list1.add(5);System.out.println(list1);ArrayList<Integer> list2 = new ArrayList<>();list2.add(11);list2.add(22);list2.add(33);list2.add(44);list2.add(55);//使用ArrayList构造LinkedListLinkedList<Integer> list3 = new LinkedList<>(list2);System.out.println(list3);}//结果为：//[1, 2, 3, 4, 5]//[11, 22, 33, 44, 55]
}

2. 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

import java.util.LinkedList;
import java.util.List;
public class Test {public static void main(String[] args) {LinkedList<Integer> list1 = new LinkedList<>();list1.add(1);   //add(elem)表示尾插list1.add(2);list1.add(3);list1.add(4);list1.add(5);System.out.println(list1.size());   //5System.out.println(list1);      //[1, 2, 3, 4, 5]//在起始位置插入0list1.add(0,0);    //add(index,elem);在index位置插入元素elemSystem.out.println(list1);      //[0, 1, 2, 3, 4, 5]list1.remove();     //remove();删除第一个元素，内部调用的是removeFirst()System.out.println(list1);  //[1, 2, 3, 4, 5]list1.removeFirst();    //removeFirst();删除第一个元素System.out.println(list1);  //[2, 3, 4, 5]list1.removeLast();     //removeLast();删除最后一个元素System.out.println(list1);  //[2, 3, 4]list1.remove(1);    //remove(index);删除index位置的元素System.out.println(list1);  //[2, 4]//contains(elem):检测elem元素是否存在，如果存在返回true，否则返回falseif(!list1.contains(1)){list1.add(0,1);}System.out.println(list1);  //[1, 2, 4]list1.addLast(1);System.out.println(list1);  //[1, 2, 4, 1]System.out.println(list1.indexOf(1));   //indexOf(elem);从前往后找第一个elem的位置 0System.out.println(list1.lastIndexOf(1));   //lastIndexOf(elem);从后往前找第一个elem的位置 3int elem = list1.get(0);    //get(index);获取指定位置元素System.out.println(elem);   // 1list1.set(0,100);   //set(index,elem);将index位置的元素设置为elemSystem.out.println(list1);  //[100, 2, 4, 1]//subList(from,to):用list1中[from,to)之间的元素构造一个新的LinkedList返回List<Integer> copy = list1.subList(0,3);System.out.println(list1);  //[100, 2, 4, 1]System.out.println(copy);   //[100, 2, 4]list1.clear();  //将list1中元素清空System.out.println(list1.size());   //0}
}

3. LinkedList的遍历

public class Test {public static void main(String[] args) {LinkedList<Integer> list = new LinkedList<>();list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);System.out.println(list);System.out.println("======for=====");for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i) + " ");}System.out.println();System.out.println("======for each=====");for(int x : list){System.out.print(x + " ");}System.out.println();System.out.println("======Iterator=====");Iterator<Integer> it = list.iterator();while(it.hasNext()){System.out.print(it.next() + " ");}System.out.println();System.out.println("======ListIterator=====");ListIterator<Integer> lit = list.listIterator();while(lit.hasNext()){System.out.print(lit.next() + " ");}System.out.println();System.out.println("======ListIterator拓展=====");ListIterator<Integer> lit2 = list.listIterator(list.size());while(lit.hasPrevious()){System.out.print(lit.previous() + " ");}}//结果为：//[1, 2, 3, 4, 5]//======for=====//1 2 3 4 5//======for each=====//1 2 3 4 5//======Iterator=====//1 2 3 4 5 //======ListIterator=====//1 2 3 4 5//======ListIterator拓展=====//5 4 3 2 1
}

ArrayList和LinkedList的区别

不同点	ArrayList	LinkedList
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持：O(1)	不支持：O(N)
头插	需要搬移元素，效率低O(N)	只需修改引用的指向，时间复杂度为O(1)
插入	空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除元素频繁

---

本篇文章到此，谢谢阅读，希望对您有帮助。