LinkedList与链表

逃离我推掉我的手 2024-02-05 18:10 74阅读 0赞

**\[本节目标\]**

**1.ArrayList的缺陷**

**2.链表**

**3.链表相关oj题**

**4.LinkedList的模拟实现**

**5.LinkedList的使用**

**6.ArratList和LinkedList的区别**

## 1. ArrayList的缺陷 ##

上篇博客已经熟悉了ArrayList的使用,并且进行了简单模拟实现,ArrayList底层使用数组来储存元素:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
     // ...
     // 默认容量是10
      private static final int DEFAULT_CAPACITY = 10;
      //...
     
      // 数组：用来存储元素
      transient Object[] elementData; // non-private to simplify nested class access
     
      // 有效元素个数
      private int size;
      public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
          this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
          this.elementData = EMPTY_ELEMENTDATA;
       } else {
          throw new IllegalArgumentException("Illegal Capacity: "+
                           initialCapacity);
       }
     }

由于其底层是一段连续空间,当在ArrayList任意位置插入或者删除元素时,就需要将后续元素往前或者往后搬移,时间复杂度O(n),效率比较低,因此ArrayList不适合任意位置插入和删除比较多的场景,因此java又引入了LinkedList,即链表结构.

## 2. 链表 ##

### 2.1 链表的概念及结构 ###

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

![67e56553a2464d449dcc858314815b40.png][]

1. 从图上可以看出来,链式结构在逻辑上是连续的,但是在物理结构上是不一定连续的.

2.现实中的结点一般都是从堆上申请出来的

3.从堆上申请的空间,是按照一定策略来分配的,两次申请的空间可能连续,也可能不连续

实际中链表的结构非常多样,以下情况结合起来就有8种链表结构:

1.单向或者双向

![598313ee55514c5e9fc373c97370fc31.png][]

2.带头或者不带头

![e443565b58b34991bf42f9da9ff0c934.png][]

3.循环或者非循环

![6a9093ddd24b42af84e4ab0e6c613fe4.png][]

虽然有很多的链表的结构,但是我们重点掌握两种:

1.无头单向非循环链表,结构简单,一般不会单独来存数据,实际中更多是作为其他数据结构的子结构.如哈希桶,图的邻接表,另外这种结构在笔试面试中出现很多.

![67e56553a2464d449dcc858314815b40.png][]

2.无头双向链表:在java中的集合框架中LinkedList底层实现就是无头双向链表

### 2.2 链表的使用和体现 ###

> // 1、无头单向非循环链表实现  
> 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() \{\}  
> \}

## 3. LinkedList的模拟实现 ##

public class MyListNode {
    
        static class ListNode {
            int value;
            public ListNode next;
            public ListNode prev;
    
            public ListNode(int value) {
                this.value = value;
            }
        }
    
        public ListNode head;
    
        public void createlist() {
            ListNode node1 = new ListNode(1);
            ListNode node2 = new ListNode(2);
            ListNode node3 = new ListNode(3);
            ListNode node4 = new ListNode(4);
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            this.head = node1;
        }
    
        public void addFirst(int data){
            Listnode node = new Listnode(data);
           if(head==null){
               head=node;
               last = node;
           }
           else{
               node.next=head;
               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;
            }
            else{
                last.next = node;
                node.prev=last;
                last =node;
            }
        }
    
        
    
        public void clear() {
            ListNode cur = head;
            while(cur != null){
                ListNode curr = cur.next;
                cur.next =null;
                cur = curr;
            }
            head = null;
            }
    
       public void remove(int key){
            Listnode cur =head;
            while(cur != null){
                if(cur.val == key){
                    head = head.next;
                    if(head==null){
                        last=null;
                     }
                    else{
                        head.prev.next= cur.next;
                        if(cur.next==null){
                            last=last.next;
                        }
                    }
                    return;
                }
                else{
                    cur =cur.next;
                }
            }
        }
    public void removeAllKey(int key) {
            Listnode cur = head;
            while (cur != null) {
                if (cur.val == key) {
                    head = head.next;
                    if (head == null) {
                        last = null;
                    } else {
                        head.prev.next = cur.next;
                        if (cur.next == null) {
                            last = last.next;
                        }
                    }
                }
                cur = cur.next;
            }
        }
    
    
       public void addIndex(int index,int data){
            Listnode node = new Listnode(data);
            int len = size();
            if(index<0 || index>size()){
                return;
            }
            if(index==0){
                addFirst(data);
            }
            if(index==size()){
                addLast(data);
            }
            Listnode cur = head;
            int count =0;
            while(count<index){
                cur=cur.next;
                count++;
            }
            cur.prev.next = node;
            node.prev=cur.prev;
            node.next=cur;
            cur.prev = node;
        }
    
        public boolean contains(int key) {
            ListNode cur = head;
            while (cur != null){
                if(cur.value == key){
                    return true;
                }
                cur = cur.next;
            }
           return false;
        }
        public int size() {
            int count = 0;
            ListNode cur = head;
            while(cur != null){
                count++;
                cur = cur.next;
            }
               return count;
           }
    
            public void display () {
                ListNode cur = head;
                while (cur.next != null) {
                    System.out.println(cur.value + " ");
                    cur = cur.next;
                }
                System.out.println(cur.value);
            }
    }

## 4. LinkedList的使用 ##

### 4.1 什么是LinkedList ###

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

![c2d19e9b774e4e2fafbf0fc3defc3d86.jpeg][]

**\[说明\]**

**1.LinkedList实现了List接口**

**2.LinkedList的底层使用了双向链表**

**3.LinkedList没有实现RandomAccess接口,因此LinkedList不支持随机访问**

**4.LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)**

**5.LinkedList比较适合任意位置插入的场景**

### 4.2 LinkedList的使用 ###

1.LinkedList的构造

![39ae58ee664e4b6a855bca741927029e.png][]

public static void main(String[] args) {
            List<Integer> list1 = new LinkedList<>();
            List<String> list2 = new ArrayList<>();
            list2.add("javase");
            list2.add("javaee");
            list2.add("数据结构");
            List<String> list3 = new LinkedList<>(list2);
        }

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

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

3.LinkedList的遍历

public static void main(String[] args) {
      LinkedList<Integer> list = new LinkedList<>();
      list.add(1);  // add(elem): 表示尾插
      list.add(2);
      list.add(3);
      list.add(4);
      list.add(5);
      list.add(6);
      list.add(7);
      System.out.println(list.size());
      // foreach遍历
      for (int e:list) {
        System.out.print(e + " ");
     }
      System.out.println();
      // 使用迭代器遍历---正向遍历
      ListIterator<Integer> it = list.listIterator();
      while(it.hasNext()){
        System.out.print(it.next()+ " ");
     }
      System.out.println();
      // 使用反向迭代器---反向遍历
      ListIterator<Integer> rit = list.listIterator(list.size());
      while (rit.hasPrevious()){
        System.out.print(rit.previous() +" ");
     }
      System.out.println();
    }

## 5.ArrayList和LinkedList的区别 ##

![a323256c3c454db4ad7a1a0d9c7bbee9.png][]

## 6. 例题(帮助大家巩固链表) ##

1. 删除链表中等于给定值 val 的所有节点。[203. 移除链表元素 - 力扣（LeetCode）][203. _ - _LeetCode]

public ListNode removeElements(ListNode head, int val) {
          if(head==null){
              return null;
          }
          ListNode pre = head;
          ListNode cur = head.next;
          while(cur != null){
              if(cur.val==val){
                  pre.next = cur.next;
                  cur=cur.next;
              }else{
                  pre = pre.next;
                  cur = cur.next;
              }
          }
          if(head.val == val){
              head = head.next;
          }
          return head;
        }

2. 反转一个单链表。[206. 反转链表 - 力扣（LeetCode）][206. _ - _LeetCode]

public ListNode reverseList(ListNode head) {
            if(head==null){
                return null;
            }
    ListNode cur =head.next;
    ListNode slow =head;
    while(cur!=null){
        ListNode curNex=cur.next;
    cur.next=slow;
    if(slow==head){
        cur.next.next=null;
    }
    slow=cur;
    cur=curNex;
    }
    return slow;
        }

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。[876. 链表的中间结点 - 力扣（LeetCode）][876. _ - _LeetCode]

public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while(fast!=null && fast.next!=null){
        fast=fast.next.next;
        slow=slow.next;
    }
    return slow;
    }

4. 输入一个链表，输出该链表中倒数第k个结点。 [面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）][02.02. _ k _ - _LeetCode]

public int kthToLast(ListNode head, int k) {
    ListNode cur=head;
    int count =0;
    while(cur!= null){
        count++;
        cur=cur.next;
    }
    cur=head;
    int a = count-k;
    while(a!=0){
        a--;
        cur=cur.next;
    }
    return cur.val;
        }

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。[21. 合并两个有序链表 - 力扣（LeetCode）][21. _ - _LeetCode]

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode node = new ListNode(-1);
    ListNode tem =  node;
    
    while(list1 != null && list2 != null){
        if(list1.val<list2.val){
           
          tem.next = list1;
          //  tem = list1;//错误
            list1=list1.next;
        }
        else
        {
            tem.next = list2;
          //  tem = list2;//错误
             list2=list2.next;
        }
       tem = tem.next;
        }
         if(list1 != null){
    tem.next = list1;
        }
        if(list2 != null){
    tem.next = list2;
        }
        return node.next;
    }

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。[面试题 02.04. 分割链表 - 力扣（LeetCode）][02.04. _ - _LeetCode]

public ListNode partition(ListNode head, int x) {
    if(head == null){
        return null;
    }
    ListNode cur = head;
    ListNode bs =null;
    ListNode be = null;
    ListNode as = null;
    ListNode ae = null;
    while(cur != null){
        if(cur.val < x){
        if(bs == null){
          be = cur;
          bs =cur;
        }else{
    be.next = cur;
    be = be.next;
        }
        }else{
    if(as == null){
        as = cur;
        ae = cur;
    }else{
    ae.next = cur;
    ae = ae.next;
    }
        }
        cur= cur.next;
        }
    if(bs==null){
        return as;
    }
    if(as !=null){
        ae.next = null;
    }
        be.next = as;
        return bs;
    }

7. 链表的回文结构。[LCR 027. 回文链表 - 力扣（LeetCode）][LCR 027. _ - _LeetCode]

public boolean isPalindrome(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    ListNode cur = slow.next;
    while(cur != null){
    ListNode curnex = cur.next;
    cur.next = slow;
    slow = cur;
    cur = curnex;
    }
    while(head != slow){
        if(head.val != slow.val){
          return false;  
        }
        if(head.next == slow){
            return true;
        }
        head = head.next;
        slow = slow.next;
    }
    return true;
        }

8. 输入两个链表，找出它们的第一个公共结点。[160. 相交链表 - 力扣（LeetCode）][160. _ - _LeetCode]

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode p1 = headA;
       ListNode p2 = headB;
       int count1 = 0;
       int count2 = 0;
    while(p1!=null){
        p1=p1.next;
    count1++;
    }
    while(p2!=null){
        p2=p2.next;
        count2++;
    }
    p1= headA;
    p2 =headB;
    int len =count1-count2;
    if(len<0){
    p1 =headB;
    p2 =headA;
    len = count2-count1;
    }
    while(len!=0){
        len--;
        p1=p1.next;
    }
    while(p1!=p2){
        p1=p1.next;
        p2=p2.next;
    }
    if(p1==null){
        return null;
    }
    return p1;
    
        }

[67e56553a2464d449dcc858314815b40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/b88e09f5423a4f6684b0506780adaa01.png
[598313ee55514c5e9fc373c97370fc31.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/3ac66940fdda440a904443e76431fb8b.png
[e443565b58b34991bf42f9da9ff0c934.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/5cceb73647ce4c17922f6385f3df7c7f.png
[6a9093ddd24b42af84e4ab0e6c613fe4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/e7aab236bd0b48059660b7c92da35600.png
[c2d19e9b774e4e2fafbf0fc3defc3d86.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/d22afa7a4d264bee825280e84d822a60.png
[39ae58ee664e4b6a855bca741927029e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/df73144888ef4f4a82cd7cb3bb4f8d01.png
[a323256c3c454db4ad7a1a0d9c7bbee9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/6be442938aa4453fb49764e7c1d81b45.png
[203. _ - _LeetCode]: https://leetcode.cn/problems/remove-linked-list-elements/description/
[206. _ - _LeetCode]: https://leetcode.cn/problems/reverse-linked-list/description/
[876. _ - _LeetCode]: https://leetcode.cn/problems/middle-of-the-linked-list/
[02.02. _ k _ - _LeetCode]: https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/
[21. _ - _LeetCode]: https://leetcode.cn/problems/merge-two-sorted-lists/
[02.04. _ - _LeetCode]: https://leetcode.cn/problems/partition-list-lcci/
[LCR 027. _ - _LeetCode]: https://leetcode.cn/problems/aMhZSa/
[160. _ - _LeetCode]: https://leetcode.cn/problems/intersection-of-two-linked-lists/