【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）头插法

主要操作：

1. 将新创建的节点的指针域更改为头节点的地址 
2. 将头节点的位置进行改变

public void addFirst(int data){//代码不能交换//必须先绑定信息ListNode listNode = new ListNode(data);listNode.next = head;head = listNode;}

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

（2）尾插法

主要操作：

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

特殊情况：

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

代码实现：

    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）固定位置插入

主要操作：

1. 找到要插入位置的前一个位置（cur）
2. 让新节点的指针域指向要插入位置的旧节点
3. 让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）删除第一个出现的元素

主要步骤：

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

代码实现：

    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）删除出现的所有元素

主要步骤：

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

代码实现：

        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遍历

        //2for (int x : list){System.out.print(x+" ");}

（3）使用迭代器

正向遍历

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

反向遍历

        //4ListIterator<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 适合频繁插入和删除的场景，例如实现栈、队列，适合元素数量动态变化的场景。