数据结构Java版（4）——链表

一、概述

? ? ? ? 链表是一种常见的数据结构，用于存储一系列具有相同类型的数据元素。它由多个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

? ? ? ? 链表与数组不同，它的节点在内存中不是连续存储的，而是通过每个节点中的指针链接在一起。这使得链表的插入和删除操作更加高效，但访问任意节点时需要遍历链表，因此访问操作的效率较低。

? ? ? ? 链表通常具有一个头节点，用于指向链表的第一个节点。如果链表为空，则头节点为空。在链表末尾，最后一个节点的指针通常为NULL，表示链表的结束。

? ? ? ? ?链表有多种类型，包括单链表、双向链表和循环链表。单链表只有一个指向下一个节点的指针，双向链表有两个指针，一个指向前一个节点，一个指向后一个节点，而循环链表的最后一个节点的指针指向链表的头节点。

? ? ? ? 链表的优点是插入和删除操作的高效性，特别是在链表的中间位置。链表的缺点是访问操作的效率较低，因为需要遍历链表。另外，由于链表的节点需要存储额外的指针，所以链表比数组占用更多的内存空间。

? ? ? ? 总之，链表是一种灵活且常用的数据结构，在许多应用中都有广泛的应用。

? ? ? ? 在Java中，因为取消了指针，所以我们只能用内部类的方式来处理节点和节点之间的关联关系。

二、链表的特点

? ? ? ? 链表是真正的动态数据结构，不同于数组的扩容和缩容，链表本身通过next来连接下一个节点，不会存在内存浪费和溢出的情况，同时，链表也是最简单的数据结构，掌握链表可以帮助我们学习更复杂的数据结构，如图和树。学习链表也有助于更深入的理解引用和递归。

? ? ? ? 在Java中，本身也给我们提供了一种链表LinkedList，它是一个泛型类，实现了栈和队列等一系列接口方法，在学习算法和开发中会经常用到，十分的灵活好用。

三、链表的实现

? ? ? ? 为了更深刻的理解链表这种数据结构，我们将自己编写一个链表，代码如下，供读者参考：

代码实现

public class LinkedList<T> {
    //节点
    class Node<T>{
        //数据域
        T data;
        //指针域
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }

        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    //链表的头节点
    private Node<T> Head;

    //链表的长度
    private int length;

    //初始化
    public LinkedList(){
        //创建头节点，下一个为首元节点
        this.Head = new Node<T>(null,null);
        this.length = 0;
    }

    //判断链表是否为空
    public boolean isEmpty(){
        return getLength()==0;
    }
    //获得链表长度
    public int getLength(){
        return this.length;
    }
    //添加节点
    //头插法
    public boolean addFirst(T data){
        return add(data,1);
    }
    //在第几个位置插入元素
    public boolean add(T data,int index){
        if(index > getLength()+1 || index < 1) return false;
        index--;
        Node<T> tempNode = this.Head;
        int index_ = 0;
        while (tempNode!=null&&index!=index_){
            tempNode = tempNode.next;
            index_++;
        }
        tempNode.next = new Node(data,tempNode.next);
        this.length++;
        return true;
    }
    //尾插法
    public boolean addLast(T data){
        return add(data,getLength()+1);
    }

    //遍历，这里借用Object.toString的方法，将其进行重写
    @Override
    public String toString() {
        Node<T> tempNode = this.Head.next;
        StringBuilder builder = new StringBuilder();
        while (tempNode!=null){
            builder.append(tempNode.data + "->");
            tempNode = tempNode.next;
        }
        builder.append("NULL");
        return builder.toString();
    }

    //查找元素是否存在
    public boolean isHave(T data){
        Node<T> tNode = this.Head.next;
        while (tNode!=null){
            if(tNode.data.equals(data)) return true;
            tNode = tNode.next;
        }
        return false;
    }

    //获取指定位置元素
    //获取首元节点元素
    public T getFirst(){
        return get(1);
    }
    //获取指定位置元素
    public T get(int index){
        if(index > getLength() || index < 1) return null;
        index--;
        Node<T> tempNode = this.Head;
        int index_ = 0;
        while (tempNode!=null&&index!=index_){
            tempNode = tempNode.next;
            index_++;
        }
        return tempNode.next.data;
    }
    //获取尾节点元素
    public T getLast(){
        return get(getLength());
    }

    //删除节点
    //删除头节点
    public T removeFirst(){
        return remove(1);
    }
    //删除指定位置节点
    public T remove(int index){
        if(index > getLength() || index < 1) return null;
        index--;
        Node<T> tempNode = this.Head;
        int index_ = 0;
        while (tempNode!=null&&index!=index_){
            tempNode = tempNode.next;
            index_++;
        }
        T res = tempNode.next.data;
        tempNode.next = tempNode.next.next;
        this.length--;
        return res;
    }
    //删除尾节点
    public T removeLast(){
        return remove(getLength());
    }

    //删除第一个指定元素的节点
    public boolean remove(T data){
        Node<T> tempNode = this.Head;
        while (tempNode.next!=null){
            if(tempNode.next.data.equals(data)){
                tempNode.next = tempNode.next.next;
                this.length--;
                return true;
            }
            tempNode = tempNode.next;
        }
        return false;
    }

    //删除链表中所有是这个元素的节点
    public int removeAll(T data){
        int count = 0;
        while (remove(data)) count++;
        return count;
    }

    //修改指定位置的值
    public boolean set(T data,int index){
        remove(index);
        return add(data,index);
    }

    //使用递归的方式删除链表元素
    public void remove_all_by_recursion(T value){
        this.Head.next = recursion_remove(value,this.Head.next);
    }
    private Node recursion_remove(T value,Node node){
        //递归终止条件
        if(node==null) return null;
        //递归操作
        if(node.data.equals(value)){
            this.length--;
            return node.next;
        }else {
            node.next = recursion_remove(value,node.next);
            return node;
        }
    }
}

测试链表

import java.util.Random;

public class testMyLinked {

    public static void main(String[] args) {
        Random random = new Random();
        LinkedList<Integer> linkedList = new LinkedList<>();
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        for(int i = 0;i < 10;i++){
            linkedList.addLast(random.nextInt(10));
            System.out.println(linkedList.toString());
        }
        linkedList.add(666,5);
        for(int i = 0;i < 10;i++){
            linkedList.addFirst(random.nextInt(10));
            System.out.println(linkedList.toString());
        }
        System.out.println(linkedList.isHave(666));
        System.out.println(linkedList.add(1145, 10));
        System.out.println(linkedList.isHave(114));
        System.out.println(linkedList.get(15));
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        System.out.println(linkedList.remove(16));
        System.out.println(linkedList.toString());
        System.out.println(linkedList.removeFirst());
        System.out.println(linkedList.removeLast());
        System.out.println(linkedList.toString());
        System.out.println(linkedList.remove(new Integer(1145)));
        System.out.println(linkedList.toString());
        System.out.println(linkedList.removeAll(new Integer(6)));
        System.out.println(linkedList.toString());
        System.out.println(linkedList.set(1919, 6));
        System.out.println(linkedList.toString());
        linkedList.remove_all_by_recursion(4);
        System.out.println(linkedList.toString());

    }
}

输出结果：