【数据结构】链表

野性酷女 2024-04-23 20:29 2阅读 0赞

> ⭐ 作者：小胡\_不糊涂  
> 🌱 作者主页：[小胡\_不糊涂的个人主页][Link 1]  
> 📀 收录专栏：[浅谈数据结构][Link 2]  
> 💖 持续更文，关注博主少走弯路，谢谢大家支持 💖

#### 链表 ####

*  1. ArrayList的缺陷
 *  2. 链表
 *   *  2.1 链表的概念
     *  2.2 无头单向非循环链表的模拟实现
     *  2.3 无头双向链表的模拟实现
 *  3. LinkedList的使用
 *   *  3.1 什么是LinkedList
     *  3.2LinkedList的使用
 *  4. ArrayList和LinkedList的区别

![在这里插入图片描述][e4717571981448629714940a02bf70d7.gif_pic_center]

## 1. 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 链表的概念 ###

> 链表是一种**物理存储结构**上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。  
> ![在这里插入图片描述][76e6140da1f44e3fa2b26e1b0d398470.png]

**链表的结构如下图所示：**  
![在这里插入图片描述][cd1fcc8b356046c3be2171b0f06cbd0c.png]

1.  从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2.  现实中的结点一般都是从堆上申请出来的
3.  从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

**实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：**

1.  单向、双向链表  
    ![在这里插入图片描述][f519b99e79704907a498c00198309e77.png]
2.  不带头、带头链表  
    ![19e98ee352264202bc7abb72e124a5c9.png][]
3.  循环、非循环链表  
    ![在这里插入图片描述][3b4b3f613ea444fba1359e78ca3b1095.png]

注：

*  无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。
 *  无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

### 2.2 无头单向非循环链表的模拟实现 ###

public class SingleLinkedList {
        
        static class ListNode{
        
            public int val;
            public ListNode next;//指向当前结点的下一个结点
    
            public ListNode(int val){
        
                this.val=val;
            }
        }
    
        public ListNode head;
    
        //创建一段链表
        public void creatList(){
        
            ListNode node1=new ListNode(3);
            ListNode node2=new ListNode(7);
            ListNode node3=new ListNode(9);
            ListNode node4=new ListNode(6);
    
            node1.next=node2;
            node2.next=node3;
            node3.next=node4;
    
            this.head=node1;
        }
    
        //头插法
        public void addFirst(int data){
        
            ListNode node=new ListNode(data);
            //判断链表是否为空
            if(this.head==null){
        
                this.head=node;
            }else{
        
                node.next=this.head;
                this.head=node;
            }
    
        }
        //尾插法
        public void addLast(int data){
        
            ListNode node=new ListNode(data);
            ListNode cur=this.head;
            if(this.head==null){
        
                this.head=node;
            }else{
        
                //找到尾巴
                while(cur.next!=null){
        
                    cur=cur.next;
                }
                cur.next=node;
            }
        }
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
        
            if(index < 0 || index > size()) {
        
                throw new PosIllegality("插入元素下标异常: "+index);
            }
            if(index == 0) {
        
                addFirst(data);
                return;
            }
            if(index == size()) {
        
                addLast(data);
                return;
            }
            //找到前一个结点
            ListNode node=new ListNode(data);
            ListNode pre=this.head;
            while(index>1){
        
                pre=pre.next;
                index--;
            }
            node.next=pre.next;
            pre.next=node;
    
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
        
            ListNode cur = this.head;
            while (cur != null) {
        
                if(cur.val == key) {
        
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key){
        
            //链表为空
            if(this.head==null){
        
                return;
            }
            //首结点==key
            if(this.head.val==key){
        
                this.head=this.head.next;
                return;
            }
    
            //其他情况
            //找前驱结点
            ListNode pre=this.head;
            while(pre.next.val==key && pre.next!=null){
        
                pre=pre.next;
            }
            if(pre.next==null){
        
                System.out.println("没有你要找的值");
                return;
            }
            pre=pre.next.next;
        }
    
        //删除所有值为key的节点
        public void removeAllKey(int key){
        
            if(this.head == null) {
        
                return;
            }
            ListNode prev = head;
            ListNode cur = head.next;
            while (cur != null) {
        
                if(cur.val == key) {
        
                    prev.next = cur.next;
                    cur = cur.next;
                }else {
        
                    prev = cur;
                    cur = cur.next;
                }
            }
            if (head.val == key) {
        
                head = head.next;
            }
        }
    
        //得到单链表的长度
        public int size(){
        
            int count = 0;
            ListNode cur = this.head;
            while (cur != null) {
        
                count++;
                cur = cur.next;
            }
            return count;
        }
    
        public void clear() {
        
            ListNode cur = head;
            while (cur != null) {
        
                ListNode curNext = cur.next;
                //cur.val = null;
                cur.next = null;
                cur = curNext;
            }
            head = null;
        }
    
        public void display() {
        
            ListNode cur = this.head;
            while (cur != null) {
        
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
            System.out.println();
        }
    }

测试类：

public static void main(String[] args) {
        
            SingleLinkedList singleLinkedList=new SingleLinkedList();
            singleLinkedList.creatList();
            singleLinkedList.addLast(10);
            singleLinkedList.display();
    
            singleLinkedList.addFirst(1);
            singleLinkedList.display();
    
            singleLinkedList.addIndex(3,10);
            singleLinkedList.display();
    
            System.out.println(singleLinkedList.contains(3));
    
            singleLinkedList.remove(10);
            singleLinkedList.display();
    
            System.out.println(singleLinkedList.size());
    
            singleLinkedList.removeAllKey(7);
            singleLinkedList.display();
    
            singleLinkedList.clear();
            singleLinkedList.display();
        }

PosIllegality异常类：

public class PosIllegality extends RuntimeException{
        
        public PosIllegality(String msg) {
        
            super(msg);
        }
    }

### 2.3 无头双向链表的模拟实现 ###

public class MyLinkedList {
        
        static class ListNode {
        
            public int val;
            public ListNode next;
            public ListNode prev;
    
            public ListNode(int val) {
        
                this.val = val;
            }
        }
    
        public ListNode head;//指向头结点
        public ListNode last;//指向尾结点
    
        //头插法
        public void addFirst(int data){
        
            ListNode node = new ListNode(data);
            if(head == null) {
        
                head = node;
                last = node;
            }else {
        
                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;
            }
        }
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
        
            int len = size();
            // 检查index是否合法
            if(index < 0 || index > len) {
        
                throw new PosIllegality("插入元素下标异常: "+index);
            }
            if(index == 0) {
        
                addFirst(data);
                return;
            }
            if(index == len) {
        
                addLast(data);
                return;
            }
            ListNode cur = findIndex(index);
            ListNode node = new ListNode(data);
            node.next = cur;
            cur.prev.next = node;
            node.prev = cur.prev;
            cur.prev = node;
        }
        //找当前节点前一个结点
        private ListNode findIndex(int index) {
        
            ListNode cur = head;
            while (index != 0) {
        
                cur = cur.next;
                index--;
            }
            return cur;
        }
    
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
        
            ListNode cur = head;
            while (cur != null) {
        
                if(cur.val == key) {
        
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
    
        //删除第一次出现关键字为key的节点
        public void remove(int key){
        
            ListNode cur = head;
            while (cur != null) {
        
                if(cur.val == key) {
        
                    if(cur == head) {
        
                        head = head.next;//head == null
                        if(head == null) {
        
                            last = null;
                        }else {
        
                            head.prev = null;
                        }
                    }else {
        
                        cur.prev.next = cur.next;
                        if(cur.next == null) {
        
                            last = last.prev;
                        }else {
        
                            cur.next.prev = cur.prev;
                        }
                    }
                    return;
                }else {
        
                    cur = cur.next;
                }
            }
        }
        //删除所有值为key的节点
        public void removeAllKey(int key){
        
            ListNode cur = head;
            while (cur != null) {
        
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
            System.out.println();
        }
    
        //得到单链表的长度
        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;
            }
            System.out.println();
        }
    
        public void clear(){
        
            head = null;
            last = null;
    
        }
    }

测试类：

public static void main(String[] args) {
        
            MyLinkedList myLinkedList = new MyLinkedList();
            myLinkedList.addLast(1);
            myLinkedList.addLast(2);
            myLinkedList.addLast(3);
            myLinkedList.addLast(4);
            myLinkedList.display();
    
            myLinkedList.addFirst(0);
            myLinkedList.display();
    
            myLinkedList.addIndex(2,9);
            myLinkedList.display();
    
            myLinkedList.remove(9);
            myLinkedList.display();
    
            myLinkedList.clear();
            myLinkedList.display();
        }

## 3. LinkedList的使用 ##

### 3.1 什么是LinkedList ###

> LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。  
> ![在这里插入图片描述][f46d9834c23b481e90fb9614a224c920.png]

在集合框架中，LinkedList也实现了List接口，具体如下：  
![在这里插入图片描述][008b54ee818646cf86a873b0be2622ce.png]  
说明：

1.  LinkedList实现了List接口
2.  LinkedList的底层使用了双向链表
3.  LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4.  .LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5.  LinkedList比较适合任意位置插入的场景

### 3.2LinkedList的使用 ###

**LinkedList的构造：**

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>LinkedList()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>public LinkedList(Collection&lt;? extends E&gt; c)</td> 
   <td>使用其他集合容器中元素构造List</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> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>解释</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean add(E e)</td> 
   <td>尾插 e</td> 
  </tr> 
  <tr> 
   <td>void add(int index, E element)</td> 
   <td>将 e 插入到 index 位置</td> 
  </tr> 
  <tr> 
   <td>boolean addAll(Collection&lt;? extends E&gt; c)</td> 
   <td>尾插 c 中的元素</td> 
  </tr> 
  <tr> 
   <td>E remove(int index)</td> 
   <td>删除 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>boolean remove(Object o)</td> 
   <td>删除遇到的第一个 o</td> 
  </tr> 
  <tr> 
   <td>E get(int index)</td> 
   <td>获取下标 index 位置元素</td> 
  </tr> 
  <tr> 
   <td>E set(int index, E element)</td> 
   <td>将下标 index 位置元素设置为 element</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td>boolean contains(Object o)</td> 
   <td>判断 o 是否在线性表中</td> 
  </tr> 
  <tr> 
   <td>int indexOf(Object o)</td> 
   <td>返回第一个 o 所在下标</td> 
  </tr> 
  <tr> 
   <td>int lastIndexOf(Object o)</td> 
   <td>返回最后一个 o 的下标</td> 
  </tr> 
  <tr> 
   <td>List subList(int fromIndex, int toIndex)</td> 
   <td>截取部分 list</td> 
  </tr> 
 </tbody> 
</table>

使用实例：

import java.util.LinkedList;
    import java.util.List;
    public class Main {
        
        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());
        }
    }

**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();
        }

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

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

[Link 1]: https://blog.csdn.net/iLoyo_
[Link 2]: http://t.csdnimg.cn/pu3jy
[e4717571981448629714940a02bf70d7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c3b54bca2d5e43b1a88916cb466b5b10.gif
[76e6140da1f44e3fa2b26e1b0d398470.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/f92d914b80bc49c089c3ee5004935c96.png
[cd1fcc8b356046c3be2171b0f06cbd0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/144f3d51586648359dfa41e667869657.png
[f519b99e79704907a498c00198309e77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/f18aa098ddaf443bb246650c700ed744.png
[19e98ee352264202bc7abb72e124a5c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/76643a2dbe8248b48b6c4e048d258d4d.png
[3b4b3f613ea444fba1359e78ca3b1095.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/8873ba50930c4034ac809a98f29c9501.png
[f46d9834c23b481e90fb9614a224c920.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/30f31111386244d89a6b3b9c98726492.png
[008b54ee818646cf86a873b0be2622ce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/c92bdd412348418cb2b72fc53a27ab87.png