java集合—— LinkedList(双链表)的理解与用法

Dear 丶 2022-11-08 06:12 143阅读 0赞

### LinkedList介绍 ###

**知识点**

*  LinkedList 是以链表实现的，插入、删除时只需要改变前后两个节点指针指向。
 *  LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用。
 *  LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
 *  LinkedList 的成员变量只有三个：头节点 first、尾节点 last、容量 size
 *  LinkedList 实现 List 接口，能对它进行队列操作。
 *  LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
 *  LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
 *  LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
 *  LinkedList 是非同步的。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70]

**LinkedList构造函数**

1.  public LinkedList(): ——生成空的链表
2.  public LinkedList(Collection col): 复制构造函数

**AbstractSequentialList简介**

LinkedList是AbstractSequentialList的子类。AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。LinkedList既然继承于AbstractSequentialList，就相当于已经实现了这些接口”。  
此外，我们若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

### LinkedList数据结构 ###

**双向链表实现：**  
Node结点的定义：是LinkedList的静态内部类，每个节点指向前一个结点和后一个结点，这就是双向链表结点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70 1]  
**LinkedList的继承关系**

java.lang.Object
       ↳     java.util.AbstractCollection<E>
             ↳     java.util.AbstractList<E>
                   ↳     java.util.AbstractSequentialList<E>
                         ↳     java.util.LinkedList<E>
    
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
        }

### LinkedList基本用法 ###

更多的情况下我们使用 ArrayList 访问列表中的随机元素更加高效，但以下几种情况 LinkedList 提供了更高效的方法。  
**1.创建一个简单的链表实例：**

import java.util.LinkedList;
    public class RunTest {
        
        public static void main(String[] args) {
        
            LinkedList<String> sites = new LinkedList<String>();
            sites.add("a");
            sites.add("b");
            sites.add("c");
            sites.add("d");
            System.out.println(sites);
        }
    }
    以上实例，执行输出结果为：[a, b, c, d]

**2.在列表开头添加元素：**

// 引入 LinkedList 类
    import java.util.LinkedList;
    
    public class RunTest {
        
        public static void main(String[] args) {
        
            LinkedList<String> sites = new LinkedList<String>();
            sites.add("a");
            sites.add("b");
            sites.add("c");
            // 使用 addFirst() 在头部添加元素
            sites.addFirst("hello");
            System.out.println(sites);
        }
    }
    以上实例，执行输出结果为：[hello, a, b, c]

**3.在列表结尾添加元素：**

// 引入 LinkedList 类
    import java.util.LinkedList;
    
    public class RunTest {
        
        public static void main(String[] args) {
        
            LinkedList<String> sites = new LinkedList<String>();
            sites.add("a");
            sites.add("b");
            sites.add("c");
            // 使用 addLast() 在尾部添加元素
            sites.addLast("hello");
            System.out.println(sites);
        }
    }
    以上实例，执行输出结果为：[a, b, c, hello]

**4.在列表开头和结尾移除元素：**

// 引入 LinkedList 类
    import java.util.LinkedList;
    
    public class RunTest {
        
        public static void main(String[] args) {
        
            LinkedList<String> sites = new LinkedList<String>();
            sites.add("a");
            sites.add("b");
            sites.add("c");
            sites.add("d");
            // 使用 removeFirst() 移除头部元素
            sites.removeFirst();
            // 使用 removeLast() 移除尾部元素
            //sites.removeLast();
            System.out.println(sites);
        }
    }

**5.获取列表开头和结尾的元素：**

// 引入 LinkedList 类
    import java.util.LinkedList;
    
    public class RunTest {
        
        public static void main(String[] args) {
        
            LinkedList<String> sites = new LinkedList<String>();
            sites.add("a");
            sites.add("b");
            sites.add("c");
            sites.add("d");
            // 使用 getFirst() 获取头部元素
            System.out.println(sites.getFirst());
            // 使用 getLast() 获取尾部元素
            //System.out.println(sites.getLast());
        }
    }

**6.使用 for 配合 size() 方法和for-each来迭代列表中的元素：**

//size()
    import java.util.LinkedList;
    public class RunTest {
        
        public static void main(String[] args) {
        
            LinkedList<String> sites = new LinkedList<String>();
            sites.add("a");
            sites.add("b");
            sites.add("c");
            sites.add("d");
            //size() 方法用于计算链表的大小。
            for (int size = sites.size(), i = 0; i < size; i++) {
        
                System.out.println(sites.get(i));
            }
        }
    }
    //for-each
    import java.util.LinkedList;
    public class RunoobTest {
        
        public static void main(String[] args) {
        
            LinkedList<String> sites = new LinkedList<String>();
            sites.add("Google");
            sites.add("Runoob");
            sites.add("Taobao");
            sites.add("Weibo");
            for (String i : sites) {
        
                System.out.println(i);
            }
        }
    }
    以上实例，执行输出结果为：
    a
    b
    c
    d

更多 API 方法可以查看：[https://www.runoob.com/manual/jdk11api/java.base/java/util/LinkedList.html][https_www.runoob.com_manual_jdk11api_java.base_java_util_LinkedList.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70]: /images/20221023/6c9937eae22447a6b815427100f3c376.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70 1]: /images/20221023/bbbe067038a842b3aa549d9aadead0ea.png
[https_www.runoob.com_manual_jdk11api_java.base_java_util_LinkedList.html]: https://www.runoob.com/manual/jdk11api/java.base/java/util/LinkedList.html