数据结构之链表（LinkedList详解）

刺骨的言语ヽ痛彻心扉 2024-04-06 11:56 41阅读 0赞

###  ###

文章目录

*  **一、什么是LinkedList？**
 *  **二、LinkedList的使用**
 *  **三、LinkedList自实现**
 *  **四、链表实现逆序打印的两种方式（递归和非递归）**
 *  **五、ArrayList和LinkedList有什么区别？**

--------------------

### **一、什么是LinkedList？** ###

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

在集合框架中，LinkedList也实现了List接口，具体如下：

![d7695e27e19e41c0af85476fdb249112.png][]

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

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

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

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

### **二、LinkedList的使用** ###

**构造方法：**

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>解释</td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      LinkedList() 
    </div> </td> 
   <td> 
    <div>
      无参构造 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      public LinkedList(Collection&lt;? extends E&gt; c) 
    </div> </td> 
   <td> 
    <div>
      使用其他集合容器中元素构造List 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

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****的常用方法：**

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>方法</td> 
   <td>解释</td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      boolean add(E e) 
    </div> </td> 
   <td> 
    <div>
      尾插 e 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      void add(int index, E element) 
    </div> </td> 
   <td> 
    <div>
      将 e 插入到 index 位置 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      boolean addAll(Collection&lt;? extends E&gt; c) 
    </div> </td> 
   <td> 
    <div>
      尾插 c 中的元素 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      E remove(int index) 
    </div> </td> 
   <td> 
    <div>
      删除 index 位置元素 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      boolean remove(Object o) 
    </div> </td> 
   <td> 
    <div>
      删除遇到的第一个 o 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      E get(int index) 
    </div> </td> 
   <td> 
    <div>
      获取下标 index 位置元素 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      E set(int index, E element) 
    </div> </td> 
   <td> 
    <div>
      将下标 index 位置元素设置为 element 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      void clear() 
    </div> </td> 
   <td> 
    <div>
      清空 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      boolean contains(Object o) 
    </div> </td> 
   <td> 
    <div>
      判断 o 是否在线性表中 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      int indexOf(Object o) 
    </div> </td> 
   <td> 
    <div>
      返回第一个 o 所在下标 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      int lastIndexOf(Object o) 
    </div> </td> 
   <td> 
    <div>
      返回最后一个 o 的下标 
    </div> </td> 
  </tr> 
  <tr> 
   <td> 
    <div>
      List&lt;E&gt; subList(int fromIndex, int toIndex) 
    </div> </td> 
   <td> 
    <div>
      截取部分 list 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

**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在物理上不一定是连续的，在逻辑上是连续的，可以做到随用随取。

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

[d7695e27e19e41c0af85476fdb249112.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/59138e64ced84d0bb6b8c3b3cd517212.png