Java数据结构之链表实现（单向、双向链表及链表反转）

前言

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

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

结点API设计：

结点类：

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、单链表

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

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

单向链表API设计

单向链表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是待插入的结点.

插入后图：

关键性代码：

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

原图如下： 

插入结点后图如下：

关键性代码：

中间任意位置插入

插入之前的原图： 

插入到链表中间位置：

关键性代码：

代码演示：

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;
}

总结

来源：https://blog.csdn.net/weixin_43725517/article/details/116904081