【java集合系列】--- LinkedList

ゝ一世哀愁。 2022-07-14 10:51 229阅读 0赞

**开篇前言--LinkedList中的基本用法**

在前面的博文中，小编介绍List接口中的ArrayList集合，List这个接口，有两个实现类，一个就是ArrayList另一个是LinkedList（链表），这两个类都实现了List接口，so。她们有很多相似的地方。LinkedList和ArrayList一样实现了List接口，但是她执行插入和删除操作时比ArrayList更加高效，因为她是基于链表的，但同时也决定了她在随机访问方面要比ArrayList弱一点。我们通过一系列的小demo来加深对LinkedList的了解。新建一个Class，取名为LinkedListTest1，编写code，addLast和addFirst方法，如下所示：

package j2se.demo;  
      
    import java.util.LinkedList;  
      
    public class LinkedListTest1 {  
        public static void main(String[] args) {  
              
            LinkedList list = new LinkedList();  
            list.add("F");  
            list.add("B");  
            list.add("D");  
            list.add("E");  
            list.add("C");  
              
            list.addLast("Z");  
            list.addFirst("A");  
              
            list.add(1,"A2");  
              
            System.out.println("最初的集合:"+list);  
              
              
        }  
      
    }

运行效果，如下图所示：

![Image 1][]

接着，我们来看一下remove的方法，编写相关代码，如下所示：

package j2se.demo;
    
    import java.util.LinkedList;
    
    public class LinkedListTest1 {
    	public static void main(String[] args) {
    		
    		LinkedList list = new LinkedList();
    		list.add("F");
    		list.add("B");
    		list.add("D");
    		list.add("E");
    		list.add("C");
    		
    		list.addLast("Z");
    		list.addFirst("A");
    		
    		list.add(1,"A2");
    		
    		System.out.println("最初的集合:"+list);
    		
    		list.remove("F");
    		list.remove(2);
    		
    		System.out.println("变化后的集合:"+list);
    		
    	}
    
    }

运行效果如下所示：

![Image 1][]

接着，我们来看set方法，编写相关代码，如下所示：

package j2se.demo;
    
    import java.util.LinkedList;
    
    public class LinkedListTest1 {
    	public static void main(String[] args) {
    		
    		LinkedList list = new LinkedList();
    		list.add("F");
    		list.add("B");
    		list.add("D");
    		list.add("E");
    		list.add("C");
    		
    		list.addLast("Z");
    		list.addFirst("A");
    		
    		list.add(1,"A2");
    		
    		System.out.println("最初的集合:"+list);
    		
    		list.remove("F");
    		list.remove(2);
    		
    		System.out.println("变化后的集合:"+list);
    		
    		Object value = list.get(2);
    		list.set(2, (String)value+"change");
    		System.out.println("最后的集合:"+list);
    		
    	}
    
    }

运行效果，如下所示：

![Image 1][]

**LinkedList底层实现--双向链表**

我们知道LinkedList底层实现是一个链表，我们来看看什么是链表，首先我们来看线性结构，在数据结构中，一般将数据结构分为两大类，线性数据结构和非线性数据结构，其中线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图。我们重点来看一下线性表的特征：

a、线性表的逻辑结构是n个数据元素的有限序列，如a1，a2，a3，...an，其中n为线性表的长度（n>=0），n=0的表称为空表；

b、在线性表中，数据元素呈线性关系，必存在唯一的称为“第一个”的数据元素；必存在唯一的称为“最后一个”的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素；除最后一个元素外，每个元素都有且只有一个后继元素；

c、所有数据元素都在同一个线性表中必须是相同的数据类型；

d、线性表按其存储结构可以分为顺序表和链表，用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表；

e、将线性表中的数据元素依次存放在某个存储区域中，所形成的表称为顺序表，一堆数组就是用顺序方式存储的线性表。

我们来看链表，对于一个顺序表来说，她存放这个元素本身就可以了，比如说3，我们存放这个3就可以了，因为她的地址是连续存放的，通过首地址就能一个一个找到后续元素的地址，但是对于链表来说，就不行，链表不是连续存放的。so，对于链表来说，光有数据还不够，必须还要有一个指向后继元素的引用才行。设计一个类，实现链表这个结构，该如何设计，应该包括哪些方法和属性呢？首先，我们需要设计一个node类，编写代码如下所示：

package j2se.demo;
    
    public class Node {
    	
    	String data;//存放节点数据本身
    	Node next;//存放指向下一个节点的引用
    	
    	public Node(String data){
    		this.data=data;
    	}
    
    }

这样，我们就定义好了Node这个类本身，接着，新建一个Class，取名为NodeTest，实现使得node1的后继是node2，node2的后继是node3；该怎么写呢？代码如下所示：

运行，如下所示：

![Image 1][]

接着，这个时候有一个node4，需要插入在node1和node2之间，编写相关代码部分，如下所示：

package j2se.demo;
    
    
    public class NodeTest {
    	
    	public static void main(String[] args) {
    		
    		Node node1 = new Node("node1");
    		Node node2 = new Node("node2");
    		Node node3 = new Node("node3");
    		
    		node1.next=node2;
    		node2.next=node3;
    		
    		System.out.println(node1.next.next.data);
    		
    		System.out.println("----------");
    		
    		Node node4  = new Node("node4");
    		node1.next=node4;
    		node4.next=node2;
    		System.out.println(node1.next.next.next.data);
    		
    		
    	}
    
    }

运行，效果如下所示：

![Image 1][]

接着，我们将node4进行删除，代码如下所示：

运行效果如下所示：

![Image 1][]  
接着，我们来看双向循环链表，使得node1的后一个元素是node2，node2的前一个元素是node1，node2的后一个元素是node3，node3的前一个元素是node2，node3的下一个元素是node1，node1的前一个元素是node3，首先我们需要定义一个Node2类，我们来看代码部分：

package j2se.demo;
    
    public class Node2 {
    	Node2 previous;
    	String data;
    	Node2 next;
    	
    	public Node2(String data){
    		this.data=data;
    	}
    
    }

接着，我们来实现，代码如下所示：

package j2se.demo;
    
    public class NodeTest2 {
    	public static void main(String[] args) {
    		Node2 node1 = new Node2("data1");
    		Node2 node2 = new Node2("data2");
    		Node2 node3 = new Node2("data3");
    
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node1;
    
    		node3.previous = node2;
    		node2.previous = node1;
    		node1.previous = node3;
    
    		System.out.println(node1.next.next.data);
    		System.out.println(node3.previous.previous.data);
    
    	}
    
    }

运行效果，如下所示：

![Image 1][]

接着，小伙伴可以对其进行插入和删除的操作，和单向链表大同小异，小伙伴们可以自己动手实现。小编为什么要讲链表呢？因为LinkedList的底层实现就是一个双向链表，这个如果明白了，LinkedList的源码也就明白了，跟进去LinkedList的源码，我们来看她的部分源码，我们首先来看LinkedList类结构的定义，如下所示：

//通过LinkedList实现的接口可知，其支持队列操作，双向列表操作，能被克隆，支持序列化
    public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
        // LinkedList的大小（指其所含的元素个数）
        transient int size = 0;
    
        /**
         * 指向第一个节点
         * 不变的: (first == null && last == null) ||
         *            (first.prev == null && first.item != null)
         */
        transient Node<E> first;
    
        /**
         * 指向最后一个节点
         * 不变的: (first == null && last == null) ||
         *            (last.next == null && last.item != null)
         */
        transient Node<E> last;
    
        ......
    }

通过上面的代码，我们知道，  
a、LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。  
b、LinkedList 实现 List 接口，能对它进行队列操作。  
c、LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。  
d、LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。  
e、LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。  
f、LinkedList 是非同步的。  
LinkedList包含了三个重要的对象：first、last 和 size。  
a、 first 是双向链表的表头，它是双向链表节点所对应的类Node的实例  
b、 last 是双向链表的最后一个元素，它是双向链表节点所对应的类Node的实例  
c、 size 是双向链表中节点的个数。  
接着我们来看一下LinkedList的构造函数，如下所示：

//构建一个空列表
        public LinkedList() {
        }
    
        /**
         * 构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回的顺序排列的
         * @param  c 包含用于去构造LinkedList的元素的collection
         * @throws NullPointerException 如果指定的collection为空
         */
        //构建一个包含指定集合c的列表
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }

LinkedList的源码部分就先介绍到这里，小伙伴可以自己点进去看看哦，List的实现接口，小编已经介绍完两个了，一个ArrayList和LinkedList，既然她们两个都是实现了List接口，那么她们有什么样的区别和联系呢？

**ArrayList && LinkedList 比较**

a、ArrayList是基于数组，LinkedList基于链表实现。  
b、对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。  
c、对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。  
d、查找操作indexOf,lastIndexOf,contains等，两者差不多。  
**小编寄语：**该博文，小编主要介绍了list接口中另一个实现类LinkedList，从LinkedList的基本方法，到LinkedList的源码部分，和ArrayList进行对比，ArrayList底层采用数组实现，LinkedList采用双向链表实现，当执行插入或者删除操作的时候，采用LinkedList比较好；当执行搜索操作的时候，采用ArrayList比较好。小伙伴在学习的过程中，可以多查一查API文档，一起加油，小伙伴们\`(\*∩\_∩\*)′。

[Image 1]: