【Java---数据结构】链表LinkedList

1. 链表的概念

链表用于存储一系列元素，由一系列节点组成，每个节点包含两部分：数据域和指针域。

数据域：用于存储数据元素

指针域：用于指向下一个节点的地址，通过指针将各个节点连接在一起，形成一个链式结构。

注意：

链表在逻辑上是连续的，空间上并不是连续的

根据指针的连接方式，链表可以分为单向链表和双向链表

注意：

单向链表和双向链表的结点存在差异

2. 单向链表

单向链表是链表的一种，它的每个节点除了存储数据外，还包含一个指针指向下一个节点地址

2.1 单向列表的节点

每个节点只有一个指针，指向下一个节点。

最后一个节点的指针指向null，表示链表结束。

代码实现：

class ListNode{ int val; ListNode next;//next指向新的节点 public ListNode(int val) { this.val = val; } }

注意： 

结点一般都是从堆上申请出来，每次在堆上申请的空间，按照一种策略来进行分配，多次申请出来的空间，可能连续，也可能不连续

2.2 链表的创建

1. 创建一个节点

2.创建第二个节点，让第一个节点的指针域存放第一个节点的地址，以此类推，可以创建出链表

代码实现：

public void createList(){ //创建节点 ListNode listNode = new ListNode(15); ListNode listNode1 = new ListNode(56); ListNode listNode2 = new ListNode(45); ListNode listNode3 = new ListNode(88); //节点连接 listNode.next = listNode1; listNode1.next = listNode2; listNode2.next = listNode3; this.head = listNode; }

注意：

不要忘记标注链表的头节点，当输出头节点时，会输出整个链表的数据

2.3 链表的种类

2.4 链表的基本操作 2.4.1 增加 （1）头插法

主要操作：

将新创建的节点的指针域更改为头节点的地址 将头节点的位置进行改变 public void addFirst(int data){ //代码不能交换 //必须先绑定信息 ListNode listNode = new ListNode(data); listNode.next = head; head = listNode; }

 注意：代码的先后顺序不能颠倒，否则获取不到listNode.next的位置 

（2）尾插法

主要操作：

将最后一个节点的指针域指向新节点的地址 

特殊情况：

链表内没有一个节点，那么让新节点成为头节点

代码实现：

public void addLast(int data){ ListNode listNode = new ListNode(data); ListNode cur = head; if(cur==null){ head = listNode; return ; } while(cur.next!=null){//关注next的指向,找到最后一个节点 cur = cur.next; } cur.next = listNode; } （3）固定位置插入

主要操作：

找到要插入位置的前一个位置（cur）让新节点的指针域指向要插入位置的旧节点让cur指针域指向新节点的地址

注意：第二步和第三步不能交换位置，如果交换，会导致cur的位置发生改变，导致无法找到要插入位置的地址

代码实现：

public void addIndex(int index,int data){ if(index<0||index>size()){ System.out.println("位置有问题"); return; } if(index == 0){ addFirst(data); return; } if(index == size()){ addLast(data); return ; } ListNode cur = head; int count = 0; ListNode listNode = new ListNode(data); while(count<index-1){ cur =cur.next; count++; } //不能互换位置 listNode.next = cur.next; cur.next = listNode; }

注意：

不要忘记检查，插入的位置是否合法

 如果插入的位置为0；那么意味着头插法，位置为元素的长度，那么就是尾插法

2.4.2 删除 （1）删除第一个出现的元素

主要步骤：

找到你要删除元素的前一个节点找到你要删除的节点进行删除操作

代码实现：

public void remove(int data){ if(head ==null){ return; } if(head.val ==data){ head = head.next; return; } //1.找到你要删除的前一个节点 ListNode cur = head; int count = 0; while(cur.next!=null){ if(cur.next.val == data){ break; } count++; cur= cur.next; } //找到要删除的节点 ListNode del = head; int delindex = 0; while (del!=null){ if(del.val ==data){ break; } delindex++; del = del.next; } //删除操作 cur.next = del.next; }

 注意：删除的具体操作就是：删除节点的前一个节点的指向发生改变，指向删除元素的指向

（2）删除出现的所有元素

主要步骤：

初始化两个节点，cur节点进行判断值是否相同，previous是cur节点的前一个结点，方便进行删除操作进行遍历链表，找到相同的值，则进行删除操作，反之将两个节点都向后移动一位

代码实现：

if(head ==null){ return; } ListNode cur = head.next; ListNode previous = head; while(cur!=null){ if(cur.val==data){ previous.next = cur.next; cur = cur.next; }else{ previous = cur;//注意，小心写成 previous.next = cur;//错误 cur = cur.next; } } if(head.val ==data){ head = head.next; } }

注意：不要忘记对头节点进行判断

2.4.3 查看 （1）查看链表是否存在元素 public boolean contains(int value){ ListNode cur = head; while(cur!=null){ if(cur.val==value){ return true; } cur = cur.next; } return false; }

 主要步骤：

采用遍历的形式，如果找到元素，则返回true，反之，返回false

2.4.4 获取链表长度 int size(){ int count = 0; ListNode cur = head; while (cur!=null){ cur = cur.next; count++; } return count; }  2.4.5 清空链表 void clear(){ ListNode cur = head; ListNode curNext ; while(cur!=null){ curNext = cur.next; cur.next = null; cur = curNext; } head = null; } }

注意： 遍历链表逐个释放节点的引用，让每个节点不再被引用

3. 快慢指针

思想：通过使用两个速度不同的指针（快指针和慢指针）来遍历数据结构，从而实现特定的功能

注意：本质就是利用指针的移动速度差异来解决问题

常见的解决情况：

（1）找出中间的节点 ListNode findListNode(Text_2 list){ ListNode mid = head; if(head == null){ return null; } if(head.next ==null){ return head; } int count = size(list); int midCount = count/2; while (midCount>0){ mid = mid.next; midCount--; } return mid; }

这是解决这种问题，我们第一个想到的方法，需要遍历两次链表，获取长度和中间节点 ，复杂度高，下面是我们引用了快慢指针：

ListNode findListNode1(){ ListNode fast = head; ListNode slow = head; while(fast!=null&&fast.next!=null){//不能交换 fast = fast.next.next; slow = slow.next; } return slow; }

核心思想：使用快慢双指针，快的是慢的二倍；那么快的到了，慢的一定就在中间

（2）找出倒数第k个节点 ListNode findListNode(int k){ if(head ==null){ return null; } if(k<=0||k>size()){ System.out.println("k取值不对"); return null; } ListNode slow = head; ListNode fast = head; int count = k-1; while (count>0){ fast = fast.next; count--; } while(fast!=null&&fast.next!=null){ fast =fast.next; slow =slow.next; } return slow; }

核心思想：快的比慢的先走了k-1个，然后每次都移动一个， 那么快的到了，满的就是倒数第k个.

先走k-1个，因为下标从0开始

4. 双向链表

双向链表是链表的一种，它的每个节点除了存储数据外，还包含两个指针：一个指向前一个节点，另一个指向下一个节点

4.1 双向列表的节点

注意：

由于有前驱指针，删除和插入操作更高效。

每个节点需要额外存储一个指针，因此比单向链表占用更多内存。

可以从头节点向后遍历，也可以从尾节点向前遍历。

代码实现：

class ListNode{ int val; ListNode prev; ListNode next; public ListNode(int val) { this.val = val; } } 4.2 LinkedList

在 Java 中，LinkedList是java.util 包中的一个类，LinkedList的底层使用了双向链表

4.3 LinkedList的使用 4.3.1 LinkedList的构造 （1）无参构造 //调用无参构造 List<Integer> list =new LinkedList<>(); （2）利用Collection构建 List<Integer> list1 =new LinkedList<>(); list1.add(1); list1.add(2); list1.add(3); System.out.println(list1); List<Integer> list2 = new LinkedList<>(list1); list2.add(2); System.out.println(list2);

 注意：会继承传入实例对象的所有元素，并且元素的顺序也会保持一致

4.3.2  LinkedList的常用API

boolean add(E e)

尾插

void add(int index, E element)

在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)

截取顺序表的一部分

（1）增加 public class Add { public static void main(String[] args) { //尾插法 LinkedList<Integer> list =new LinkedList<>(); list.add(1); list.add(2); list.add(3); System.out.println(list); //插入固定位置 LinkedList<Integer> list1 = new LinkedList<>(); list1.add(0,1); list1.add(0,6); list1.add(1,9); System.out.println(list1); //尾插所有元素 Integer[] array = {9,99,999}; list.addAll(Arrays.asList(array)); System.out.println(list); } } （2）删除 public class Remove { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); //删除下标的数 list.remove(2); System.out.println(list); //删除第一个出现的数 list.remove(new Integer(2)); System.out.println(list); } } （3）修改 public class Set { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.set(1,999); System.out.println(list); } } （4）获取 public class Get { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); int x = list.get(2); System.out.println(x); } } （5）清空 public class Clear { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.clear(); System.out.println(list); } } （6）查找 public class Contains { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); // 判断元素是否在表中 Boolean x = list.contains(2); System.out.println(x); // 返回第一个元素所在的下标 int a = list.indexOf(2); System.out.println(a); // 返回最后一个元素所在的下标 int b = list.lastIndexOf(2); System.out.println(b); } } （7）截取 public class Sublist { public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(6); list.add(9); // LinkedList<Integer> list1 = new LinkedList<>(list.subList(1,4));//创建新的对象，进行操作，不会影响原来列表的数据 //subList返回值是List类型 List<Integer> list1 = list.subList(1,4); list1.add(999); list1.add(888); list1.set(0,111); System.out.println(list1); System.out.println(list); } }  4.3.3 LinkedList的遍历 （1）for循环遍历 //1. for (int i = 0; i < list.size(); i++) { System.out.print(list.get(i)+" "); } System.out.println(); （2）for-each遍历 //2 for (int x : list){ System.out.print(x+" "); } （3）使用迭代器

正向遍历

//3 Iterator<Integer> iterator = list.listIterator();//传数据 while (iterator.hasNext()){ System.out.print(iterator.next()+" "); } System.out.println();

反向遍历

//4 ListIterator<Integer> listIterator = list.listIterator(list.size()); while (listIterator.hasPrevious()){ System.out.print(listIterator.previous()+" "); } System.out.println();

注意：

（从前往后）while循环中的判断条件表示：是否存在下一个元素，如果存在，则获取迭代器的下一个元素并输出，因为 next 方法，所以在每次调用后进行移动1位

5. ArrayList和LinkedList的区别

差别

ArrayList

LinkedList

底层实现

基于动态数组实现

基于双向链表实现

访问效率

随机访问效率高

随机访问效率低

插入和删除效率

尾部插入和删除效率高

中间或头部插入和删除效率低

任意位置插入和删除效率高

内存占用

内存占用较少，因为只需要存储数据和数组容量。

可能存在内存浪费，因为数组会预留一定的容量

内存占用较多，因为每个节点需要存储数据以及前后指针。

总结：

ArrayList  适合频繁访问元素的场景，例如随机读取数据，适合元素数量相对固定的场景。

LinkedList 适合频繁插入和删除的场景，例如实现栈、队列，适合元素数量动态变化的场景。