数据结构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的方法，将其进行重写@Overridepublic 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());}
}

输出结果：