数据结构-LinkedList和链表

1.链表

1.1为什么要引入链表

上一篇文章中我们先容了ArrayList，ArrayList的底层是通过数组实现的，具有随机访问服从高等特点，那么我们为什么还需要引入链表呢?
这是因为ArrayList底层通过数组实现，当在ArrayList任意位置(除了末了一位)举行插入和删除操作时，就需要将后续的元素整体向前大概向后举行搬移，时间复杂度为O(n)，服从比较低，由此可见ArrayList很不适合在一些插入大概删除操作较多的场景，而java聚集中引入了链表，可以很好改善这个问题
1.2链表的概念和结构

链表是一种物理存储上非连续的存储结构，数据元素上的逻辑顺序是通过链表中的引用实现的。差别于数组，链表的物理存储单元可以分散在内存中的任意位置，通过节点(每个节点包含两部门：数据域和指针域。数据域用于存储数据元素，指针域则存储指向下一个节点的引用)之间的引用将它们连接起来形成一个线性序列
在Java中用对象引用代替指针
链表的结构多种多样，主要分为以下6种结构：
1.单向链表或双向链表

2.带头链表大概不带头链表

3.循环链表大概非循环链表

 
1.3实现一个单链表

1. public class SingleLinkedList{
2.     //头插法
3.     public void addFirst(int data){}
4.     //尾插法
5.     public void addLast(int data){}
6.     //任意位置插入
7.     public void addIndex(int index,int data){}
8.     //查询链表中是否含有关键字key
9.     public boolean contains(int key){}
10.     //删除第一次出现关键字key的节点
11.     public void remove(int key){}
12.     //删除所有值为key的节点
13.     public void removeAllKey(int data){}
14.     //得到单链表的长度
15.     public int size(){}
16.     //清空所有节点，清空单链表
17.     public void clear(){}
18.     //打印单链表
19.     public void display(){}
20. }

复制代码

 实现思路：
1.addFirst(int data)在单链表头部举行插入操作，只需要创建一个新的节点将新节点的value属性赋值为data，并将新节点的next指向原来链表的头部节点即可
2.addLast(int data)在单链表尾部举行插入操作，只需要创建一个新的节点将新节点的value属性赋值为data，并将原链表尾部的节点的next指向新的节点即可
3.addIndex(int pos,int data)在链表指定位置插入元素，起首要判断插入的位置是否正当，如果正当则分别需要修改要将原来插入位置的元素的next指向新节点，而且新节点的next要指向插入位置背面的那个节点
4.contains(int key)判断链表是否包含元素key，只需要依次遍历链表，获取到每个节点的元素并举行判断
5.remove(int key)删除元素key，遍历链表，找到key所在的位置，将key前一个元素的next指向key背面的元素即可
6.removeAllKey(int key)删除元素值为key的全部元素，每找到一个值为key的元素要举行判断key是否有前后节点，再举行相应的删除操作
7.size()返回链表中的节点个数，可以通过遍历链表并设置计数器，通过计数器统计链表中结点的个数
8.display()打印链表，遍历并依次打印每个节点的元素
 
2.LinkedList

2.1什么是LinkedList

LinkedList是Java聚集框架中的链表，LinkedList是基于双向链表实现的，由于链表中没有将元素存储在连续的空间内，元素存储在单独的节点中，然后通过引用将节点连接起来，因此在任意位置插入大概删除元素，不需要搬移元素，服从比较高。

LinkedList中的节点结构： 

 
说明：
1.LinkedList实现了List接口
2.LinkedList的底层使用了双向链表
3.LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4.LinkedList的任意位置插入和删除操作服从比较高，时间复杂度为O(1)
5.LinkedList比较适合插入删除比较多的场景
6.LinkedList的访问服从比较低，时间复杂度为O(n)
 
2.2LinkedList的构造方法

方法	表明
LinkedList()	无参构造
public LinkedList(Collection<? extends E> c)	使用其他聚集容器种的元素构造List

代码演示：

1. public class Test {
2.     public static void main(String[] args) {
3.         //构造一个空的LinkedList
4.         List<Integer> list1=new LinkedList<>();
5.         System.out.println(list1);
7.         List<String> list=new java.util.ArrayList<>();
8.         list.add("hajimi");
9.         list.add("hahaha");
10.         list.add("lalala");
11.         //使用ArrayList构造LinkedList
12.         List<String> list2=new LinkedList<>(list);
13.         System.out.println(list2);
14.     }
15. }

复制代码

 
2.3LinkedList的常用方法

方法	表明
boolean add(E,e)	在尾部插入元素e
void add(int index,E e)	将元素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 e)	将下标为index位置的元素设置为e
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

代码演示：
 

1. import java.util.*;
3. public class Test {
4.     public static void main(String[] args) {
5.         List<String> list=new LinkedList<>();
6.         //在链表末尾插入元素
7.         list.add("My");
8.         list.add("name");
9.         list.add("hajimi");
10.         System.out.println(list);
11.         //在指定位置插入元素
12.         list.add(2,"is");
13.         System.out.println(list);
14.         list.add(4,"king");
15.         System.out.println(list);
16.         //删除指定位置的元素
17.         list.remove(4);
18.         System.out.println("进行删除操作后的链表"+list);
19.         //删除指定元素
20.         list.remove("My");
21.         System.out.println("进行删除操作后的链表"+list);
22.         //获取指定位置的元素
23.         System.out.println(list.get(2));
24.         //将指定位置下标的元素设置为e
25.         System.out.println(list.set(0,"Your name"));
26.         System.out.println(list);
27.         //判断线性表中是否包含某元素
28.         System.out.println(list.contains("hajimi"));
29.         list.add("hajimi");
30.         //返回指定元素第一个出现的下标
31.         System.out.println(list.indexOf("hajimi"));
32.         //返回指定元素最后一次出现的下标
33.         System.out.println(list.lastIndexOf("hajimi"));
34.         //截取部分链表内容
35.         List<String> partList;
36.         partList=list.subList(0,3);
37.         System.out.println("截取的部分："+partList);
38.         //在链表尾部插入其他容器的所有元素
39.         list.addAll(partList);
40.         System.out.println(list);
41.         //清空链表中的所有元素
42.         list.clear();
43.         System.out.println(list);
44.     }
45. }

复制代码

 
2.4LinkedList的遍历

LinkedList遍历主要有3中方式：
1.使用for循环搭配链表长度举行遍历
2.使用foreach循环
3.使用迭代器举行遍历
代码演示：

1. import java.util.*;
3. public class Test {
4.     public static void main(String[] args) {
5.         List<String> list=new LinkedList<>();
6.         list.add("My");
7.         list.add("name");
8.         list.add("is");
9.         list.add("hajimi");
10.         list.add("king");
11.         list.add("!");
12.         //使用for循环搭配链表长度进行遍历链表
13.         for (int i=0;i<list.size();i++){
14.             System.out.print(list.get(i)+" ");
15.         }
16.         System.out.println();
17.         //使用foreach循环遍历链表
18.         for(String s:list){
19.             System.out.print(s+" ");
20.         }
21.         System.out.println();
22.         //使用迭代器遍历链表
23.         //正向遍历
24.         ListIterator<String> it= list.listIterator();
25.         while(it.hasNext()){
26.             System.out.print(it.next()+" ");
27.         }
28.         System.out.println();
29.         //反向遍历
30.         ListIterator<String> rit= list.listIterator(list.size());
31.         while (rit.hasPrevious()){
32.             System.out.print(rit.previous()+" ");
33.         }
34.     }
35. }

复制代码

2.5实现一个LinkedList

 LinkedList原码中节点的结构如下：

  实现一个泛型为Integer的链表，代码演示：

3. public class MyLinkedList2 {
4.     static class ListNode{
5.         private ListNode prev;
6.         private int val;
7.         private ListNode next;
9.         public ListNode(int val) {
10.             this.val = val;
11.         }
12.     }
13.     public ListNode head;
14.     public ListNode tail;
15.     public MyLinkedList2(){
17.     }
18.     //头插法
19.     public void addFirst(int data){
20.         ListNode newNode=new ListNode(data);
21.         if(head==null){
22.             head=tail=newNode;
23.         }else {
24.             newNode.next=head;
25.             head.prev=newNode;
26.             head=newNode;
27.         }
28.     }
29.     //尾插法
30.     public void addLast(int data){
31.         ListNode newNode=new ListNode(data);
32.         if(head==null){
33.             head=tail=newNode;
34.         }else {
35.             newNode.prev=tail;
36.             tail.next=newNode;
37.             tail=newNode;
38.         }
39.     }
40.     //任意位置插入,第一个数据节点为0号下标
41.     public boolean addIndex(int index,int data){
42.         if(index<0||index>size()){
43.             System.out.println("要插入的位置不合法");
44.             return false;
45.         }
46.         if(index==0){
47.             addFirst(data);
48.             return true;
49.         }
50.         if(index==size()){
51.             addLast(data);
52.             return true;
53.         }
54.         ListNode cur=head;
55.         while(index!=0){
56.             cur=cur.next;
57.             index--;
58.         }
59.         ListNode newNode=new ListNode(data);
60.         newNode.next=cur;
61.         newNode.prev=cur.prev;
62.         cur.prev.next=newNode;
63.         cur.prev=newNode;
64.         return true;
65.     }
66.     //查找是否包含关键字key是否在单链表当中
67.     public boolean contains(int key){
68.         if (head==null){
69.             System.out.println("链表为空");
70.             return false;
71.         }
72.         ListNode cur=head;
73.         while (cur!=null){
74.             if(cur.val==key){
75.                 System.out.println("找到了!");
76.                 return true;
77.             }
78.             cur=cur.next;
79.         }
80.         System.out.println("没找到");
81.         return false;
82.     }
83.     //删除第一次出现关键字为key的节点
84.     public void remove(int key){
85.         if (head==null){
86.             System.out.println("链表中没有元素，无法进行删除");
87.             return;
88.         }
89.         ListNode cur=head;
90.         while (cur!=null){
91.             if(cur.val==key){
92.                 //判断是否是链表尾部删除
93.                 if(cur.next==null){
94.                     cur.prev.next=null;
95.                     tail=tail.prev;
96.                 }
97.                 //删除中间节点操作
98.                 cur.prev.next=cur.next;
99.                 cur.next.prev=cur.prev;
100.             }
101.             cur=cur.next;
102.         }
103.         //判断首节点情况
104.         if(head.val==key){
105.             //如果链表只有一个节点，需要进行特殊处理
106.             if(head.next!=null){
107.                 head=head.next;
108.                 head.prev=null;
109.             }else {
110.                 head=null;
111.             }
112.         }
113.     }
114.     //删除所有值为key的节点
115.     public void removeAllKey(int key){
116.         if(head==null){
117.             return;
118.         }
119.         ListNode cur=head.next;
120.         while(cur!=null){
121.             if(cur.val==key){
122.                 if(cur.next==null){
123.                     cur.prev.next=null;
124.                     tail=tail.prev;
125.                 }else{
126.                     cur.prev.next=cur.next;
127.                     cur.next.prev=cur.prev;
128.                 }
129.             }
130.             cur=cur.next;
131.         }
132.         if(head.val==key){
133.             if(head.next==null){
134.                 head=null;
135.             }else{
136.                 head=head.next;
137.                 head.prev=null;
138.             }
139.         }
140.     }
141.     //得到单链表的长度
142.     public int size(){
143.         int count=0;
144.         ListNode cur=head;
145.         while(cur!=null){
146.             cur=cur.next;
147.             count++;
148.         }
149.         return count;
150.     }
151.     public void display(){
152.         ListNode cur=head;
153.         if(head==null){
154.             return;
155.         }
156.         while(cur!=null){
157.             System.out.print(cur.val+" ");
158.             cur=cur.next;
159.         }
160.         System.out.println();
161.     }
162.     public void clear(){
163.         ListNode cur=head;
164.         if(head==null){
165.             return;
166.         }
167.         while(cur!=null){
168.             ListNode curNext=cur.next;
169.             cur.prev=null;
170.             cur.next=null;
171.             cur=curNext;
172.         }
173.         //处理还在引用的head和tail
174.         head=null;
175.         tail=null;
176.     }
177. }

复制代码

对上述代码举行运行测试：

1. public class Test {
2.     public static void main(String[] args) {
3.         MyLinkedList2 myLinkedList2=new MyLinkedList2();
4.         myLinkedList2.addLast(1);
5.         myLinkedList2.addLast(2);
6.         myLinkedList2.addFirst(3);
7.         myLinkedList2.addIndex(2,6);
8.         myLinkedList2.addIndex(0,5);
9.         myLinkedList2.addIndex(1,4);
10.         myLinkedList2.display();
11.         System.out.println(myLinkedList2.contains(6));
12.         myLinkedList2.remove(6);
13.         myLinkedList2.display();
14.         myLinkedList2.addFirst(1);
15.         myLinkedList2.display();
16.         myLinkedList2.removeAllKey(1);
17.         myLinkedList2.display();
18.         System.out.println(myLinkedList2.size());
19.         myLinkedList2.clear();
20.         myLinkedList2.display();
21.     }
22. }

复制代码

3.LinkedList的特点

LinkedList的特点主要体如今以下几个方面：
1.数据存储的方式
LinkedList是通过一系列节点组成的，每个节点都包含三个部门，数据元素，指向前一个节点的引用和指向后一个节点的引用，链表的内存是动态分配的，每个节点的内存空间是独立分配的，使得链表的巨细灵活可调
2.操作服从
在链表头部大概尾部插入和删除元素操作的时间复杂度为O(1)，如果已经得到目标节点的引用，举行插入和删除操作的时间复杂度为O(1)，但如果没有则需要从头遍历找到目标位置，时间复杂度为O(n)
链表不支持随机访问，方位任意元素都需要从头开始举行遍历，时间复杂度为O(n)
3.内存使用
每个节点除了存取数据元素外，还需要存储引用，有额外的内存开销。链表的内存分配时动态的，不会像数组那样分配固定的巨细
4.适用场景
适合插入和删除频仍的场景，不适合随机访问的场景，适合数据量不确定的场景(动态扩展，不外多浪费空间)


4.LinkedList和ArrayList的区别

差别点	ArrayList	LinkedList
存储空间上	物理上连续的	逻辑上连续，物理上不肯定连续
随机访问	支持，时间复杂度O(1)	不支持，时间复杂度O(n)
插入/删除	需要搬运元素，服从低，时间复杂度O(n)	只需要修改引用的指向，时间复杂度O(1)
扩容机制	当数组空间不敷时，会创建一个更大的数组并复制原数据	动态分配内存，每次插入时动态分配新节点
内存使用	内存分配连续，大概有空间浪费（预留空间），但内存使用服从较高。	每个节点需要额外存储指针，内存使用相对较高。
适用场景	元素频仍访问的场景	插入删除频仍的场景

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。