Java数据结构之链表及实现

阳光穿透心脏的1/2处 2023-01-21 14:23 100阅读 0赞

之前学习的**顺序表查询非常快**，时间复杂度为O(1)，但是**增删改效率非常低**，因为每一次增删改都会元素的移动。可以使用另一种存储方式-链式存储结构。

链表是一种物理存储单元上非连续、非顺序的存储结构。链表由一序列的结点（**链表中的每一个元素成为结点**）组成。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70][]

**结点API设计**：

<table> 
 <tbody> 
  <tr> 
   <td><strong>类名</strong></td> 
   <td><strong>Node</strong></td> 
  </tr> 
  <tr> 
   <td>构造方法</td> 
   <td>Node(T t,Node next) 创建Node对象</td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td> <p>T item：存储数据</p> <p>Node next ：指向下一个结点</p> </td> 
  </tr> 
 </tbody> 
</table>

**结点类**：

public class Node<T>{
        Node next;
        private T item;
    
        public Node(Node next, T item) {
            this.next = next;
            this.item = item;
        }
    }

**生成链表**：

public class TestNode {
        public static void main(String[] args) {
            // 生成结点
            Node<Integer> one = new Node<Integer>(null,12);
            Node<Integer> two = new Node<Integer>(null,16);
            Node<Integer> three = new Node<Integer>(null,11);
            Node<Integer> four = new Node<Integer>(null,10);
            //生成链表
            one.next = two;
            two.next = three;
            three.next =four;
        }
    }

## 1、单链表 ##

单向链表是链表的一种，它有**多个结点组成**，**每个结点**都由**一个数据域**和**一个指针**组成，**数据域用来存储数据**，**指针域用来指向其后结点**。

链表的**头结点**的**数据域不存储数据**，指针域指向第一个真正存储数据的结点。

![20210517232105853.png][]

### 单向链表API设计 ###

<table> 
 <tbody> 
  <tr> 
   <td><strong>类名</strong></td> 
   <td><strong>LinkList</strong></td> 
  </tr> 
  <tr> 
   <td>构造方法</td> 
   <td>LinkList() ：创建LinkList对象</td> 
  </tr> 
  <tr> 
   <td>成员变量</td> 
   <td> <p>private Node head;记录首结点</p> <p>private int N; 记录链表的长度</p> </td> 
  </tr> 
  <tr> 
   <td>成员内部类</td> 
   <td>private class Node;结点类</td> 
  </tr> 
  <tr> 
   <td>成员方法</td> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td>public void clear()</td> 
       <td>清空链表</td> 
      </tr> 
      <tr> 
       <td>public boolean isEmpty()</td> 
       <td>判断链表是否为空，是返回true</td> 
      </tr> 
      <tr> 
       <td>public int length()</td> 
       <td>获取链表中的元素个数</td> 
      </tr> 
      <tr> 
       <td>public T get(int i)</td> 
       <td>读取并返回链表中的第i个元素的值</td> 
      </tr> 
      <tr> 
       <td> <p>public void insert(T t)</p> </td> 
       <td>往链表中插入一个元素</td> 
      </tr> 
      <tr> 
       <td>public void insert(T t,int i)</td> 
       <td>在链表的第i位置插入一个值为t的数据元素</td> 
      </tr> 
      <tr> 
       <td>public T remove(int i)</td> 
       <td>删除并返回删除链表中的第i个数据元素</td> 
      </tr> 
      <tr> 
       <td>public int indexof(T t)</td> 
       <td>返回链表中首次出现的指定的数据元素的序号，如不存在，则返回-1</td> 
      </tr> 
     </tbody> 
    </table></td> 
  </tr> 
 </tbody> 
</table>

### 单向链表Java代码实现 ###

package com.ycy.Algorithm.LinkList;
    
    
    import java.util.Iterator;
    
    /**
     * 链表的head是不可以动的
     * @param <T>
     */
    public class LinkList<T> implements Iterable<T>{
    
        private Node head;//头结点，链表的head是不可以动的
        private int N;//结点个数
        public LinkList() {
            this.head = new Node(null,null);
            N = 0;
        }
        /**
         * 结点内部类
         */
        private class Node{
            //存储数据
            T item;
            //下一个结点
            Node next;
            public Node(T item,Node next) {
                this.item = item;
                this.next = next;
            }
    
        }
        /**
         * 清空链表
         */
        public void clear(){
            head.item=null;
            head.next=null;// 头节点next为null就是空链表
            this.N=0;
        }
        /**
         * 判断链表是否为空
         */
        public boolean isEmpty(){
            return this.N==0;
        }
        /**
         * 获取链表的长度
         */
        public int length(){
            return this.N;
        }
        /**
         * 读取链表第i位置的元素值并返回
         */
        public T get(int i){
            //非法性检查
            if(i<0 || i > this.N){
                throw new RuntimeException("位置不合法");
            }
            // n也是指向头结点
            Node n = head;
            for(int index=0; index<i; index++){
                n = n.next;
            }
            return n.item;
        }
        /**
         * 往链表中插入数据t
         */
        public void insert(T t){
            // head不可以移动，不然就无法在找到链表
            // 定义一个临时的Node也指向head的指针就可以通过移动该指针就可以
            Node n = head;
            // 获取尾节点
            while(true){
                // 当刚好就一个节点时（头节点）
                if(n.next == null){
                    break;
                }
                n = n.next;
            }
            //当为空表时，就可以插入
            Node node = new Node(t, null);
            n.next =node;
            this.N ++;
        }
    
        /**
         * 在第i位置上插入数据t
         */
        public void insert(T t,int i){
            // 非法性检查
            if(i < 0 || i > this.N){
                throw  new RuntimeException("插入位置❌");
            }
            Node pre = head;
            for(int index=0;index <= i-1; index++){
                pre = pre.next;
            }
            Node current = pre.next;
            //先链接后面结点
            Node newNode = new Node(t,null);
            pre.next = newNode;
            newNode.next = current;
            this.N++;
        }
        /**
         * 移除并返回第i位置的元素值
         */
        public  T remove(int i){
            // 非法性检查
            if(i < 0 || i >this.N){
                throw  new RuntimeException("删除位置有误");
            }
            Node n =head;
            for(int index=0;index <= i-1;index ++){
                 n = n.next;
            }
            //要删除的节点
            Node curr = n.next;
            n.next = curr.next;
            this.N--;//结点个数减一
            return curr.item;
        }
        //查找元素t在链表中第一次出现的位置
        public int indexof(T t){
            Node n = head;
            for(int i = 0; n.next != null;i++){
                n =n.next;
                if(n.item.equals(t)){
                    return i;
                }
            }
            return -1;
        }
    
        @Override
        public Iterator iterator() {
            return new Iterator() {
                Node n =head;
                @Override
                public boolean hasNext() {
                    return n.next !=null;
                }
                @Override
                public Object next() {
                    //下移一个指针
                    n = n.next;
                    return n.item;
                }
            };
        }
    }

**补充一点**：**链表的赋值给新的链表**后，两个链表是会**相会影响的**，说白了就是把**地址赋值**给它了，他们操作是同一块内存的同一个对象。Node n = head;把head赋值给n，现在对n操作也是会影响head的

其中**提供遍历方式**，实现Iterable接口。

测试代码：

public class test {
        public static void main(String[] args) {
            LinkList<Integer>linkList = new LinkList<>();
            linkList.insert(1);
            linkList.insert(2);
            linkList.insert(4);
            linkList.insert(3);
            linkList.insert(1,2);
            for (Integer i : linkList) {
                System.out.print(i+" ");
            }
        }
    }

运行结果：

> D:\\Java\\jdk-12.0.2\\bin\\java.exe "-javaagent:D:\\IDEA\\IntelliJ IDEA 2019.1\\lib\\idea\_rt.jar=3542:D:\\IDEA\\IntelliJ IDEA 2019.1  
> 1 2 1 4 3

学习完链表还是需要加以练习的，可以在LeetCode上刷题加深理解。

## 2、双向链表 ##

> 头插法：新增节点总是插在头部

便于理解可以画图表示

头插法：原图，node是待插入的结点.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 1][]

插入后图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 2][]

关键性代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 3][]

> 尾插法：新增节点总是插在尾部

原图如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 4][]

插入结点后图如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 5][]

关键性代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 6][]

> 中间任意位置插入

插入之前的原图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 7][]

插入到链表中间位置：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 8][]

关键性代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 9][]

代码演示：

>     class MyLinkedList {
>         Node head;//定义双向链表的头节点
>         Node last;//定义双向链表的尾节点
>     
>         //打印双向链表
>         public void disPlay() {
>             Node cur = this.head;
>             while (cur != null) {
>                 System.out.print(cur.val + " ");
>                 cur = cur.next;
>             }
>             System.out.println();
>         }
>     
>         //求双向链表的长度（之后addIndex代码会用到）
>         public int size() {
>             int count = 0;
>             Node cur = this.head;
>             while (cur != null) {
>                 count++;
>                 cur = cur.next;
>             }
>             return count;
>         }
>     
>         //头插法
>         public void addFirst(int data) {
>             Node node = new Node(data);//定义一个用作插入的节点
>             //1.假设双向链表为空
>             if (this.head == null) {
>                 this.head = node;
>                 this.last = node;
>             } else {
>                 //2.双向链表不为空的情况下
>                 //不懂请看上面的图解，就很简单了
>                 node.next = this.head;
>                 this.head.prev = node;
>                 this.head = node;
>             }
>         }
>     
>         //尾插法（与头插法类似）
>         public void addLast(int data) {
>             //定义一个用作插入的节点
>             Node node = new Node(data);
>             //1.假设双向链表为空
>             if (this.head == null) {
>                 this.head = node;
>                 this.last = node;
>             } else {
>                 //2.双向链表不为空的情况下
>                 //不懂请看上面的图解，就很简单了
>                 last.next = node;
>                 node.prev = last;
>                 last = node;
>             }
>         }
>     
>         //在任意位置插入
>         public void addIndex(int index, int data) {//形参index为插入元素位置，data为插入的数值
>             //定义一个用作插入的节点
>             Node node = new Node(data);
>             Node cur = this.head;//定义一个cur用作遍历双向链表
>             //1、判断插入位置的合法性
>             if (index < 0 || index > size()) {
>                 System.out.println("插入位置不合法！！！");
>                 return;
>             }
>             //2、假设插入位置为头结点的情况下，即就是头插法
>             if (index == 0) {
>                 addFirst(data);//调用头插法代码
>                 return;
>             }
>             //3、假设插入位置为尾结点的情况下，即就是尾插法
>             if (index == size()) {
>                 addLast(data);//调用尾插法代码
>                 return;
>             }
>             //4、在中间任意位置的情况下
>             while (index != 0) {
>                 cur = cur.next;
>                 index--;
>             }
>             //不懂请看上面的图解，就很简单了
>             //核心代码
>             node.next = cur;
>             node.prev = cur.prev;
>             cur.prev = node;
>             node.prev.next = node;
>         }
>     }
>     
>     //双向链表的节点结构
>     class Node {
>         int val;
>         Node prev;
>         Node next;
>     
>         Node(int val) {
>             this.val = val;
>         }
>     }

## 3、链表反转 ##

public void reverse(){
            if(N==0){
            //当前是空链表，不需要反转
                return;
            }
            reverse(head.next);
    }
        /**
         * @param curr 当前遍历的结点
         * @return 反转后当前结点上一个结点
         */
    public Node reverse(Node curr){
            //已经到了最后一个元素
            if(curr.next==null){
            //反转后，头结点应该指向原链表中的最后一个元素
              head.next=curr;
              return curr;
            }
           //当前结点的上一个结点
           Node pre=reverse(curr.next);
           pre.next=curr;
           //当前结点的下一个结点设为null
           curr.next=null;
           //返回当前结点
           return curr;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70]: /images/20221020/c1206dfc96294a3eb9a0b8ad76f2d92e.png
[20210517232105853.png]: /images/20221020/936397ad03c149229bb2950248122c5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 1]: /images/20221020/3aa9e6e3f45c40f3afed9a32e27ec2d0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 2]: /images/20221020/243febbde85249399291425489ce4b9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 3]: /images/20221020/85ad09799f8a45db902070bedbd4e4fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 4]: /images/20221020/38e154acbac64ead837b8f58eb95d70c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 5]: /images/20221020/ab09033729294dde995d33d405f44e63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 6]: /images/20221020/73fb451b8d49464a83f1d5b666f8fd9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 7]: /images/20221020/b978f1b54e22441aac4882dd0368c843.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 8]: /images/20221020/d7328b84783343a4bb0f07172a79d3ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 9]: /images/20221020/9f5a9e269fcc416d839fef139c38748e.png