Java语言之LinkedList和链表的实现方法

一.链表概念

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。

逻辑结构：

注：1、如上图，相当于火车车厢，每一节都相连在一起。

       2、各个结点连接的方式：通过地址连接，在内存当中，相邻结点在内存中不一定相邻。

       3、所有结点都在  堆 中申请出来。

       4、 每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

二.链表的分类 

 1.单向、双向链表

 注：无论单向还是双向，都是一个结点存储着下（上）一个结点。

2.带头、不带头结点 链表

 注：无头和带头结点的主要区别：有一个起始结点。

3.循环、非循环链表 

循环链表，就是指：头、尾结点有联系。

在链表结构中，这是主要的链表，但是这些链表种类还可以结合，如：带头双向循环链表、双向循环链表等等。

链表的种类很多，但都大同小异，我们主要学习两种链表：

1、无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。              

2、无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表

三.无头单向非循环链表的实现

3.1创建简单链表

重点：每个结点存储着下一个结点的地址。

创建链表代码实现：

public class SingleLinkedList {
     static class List{
       int item;   //存储数据
       List next;   //指向下一个结点
       public List(int item) {
           this.item = item;
       }
       public List() {};
   }
//各种链表实现方法
//头插法
public void addFirst(int data){
}
   //尾插法
public void addLast(int data){
}
   //任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
}
   //查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
return false;
}
   //删除第一次出现关键字为key的节点
public void remove(int key){
}
   //得到单链表的长度
public int size(){
   return -1;
}
   //链表的清空
public void clear() {
}
   //展示链表
public void display() {}

3.2 链表基本方法实现

1.遍历链表元素

public void show() {
       //这里不是定义了一个节点 这里只是一个引用
       ListNode cur = head;
       while (cur != null) {
           System.out.print(cur.val+" ");
           cur = cur.next;
       }
       System.out.println();
   }

2.获取链表长度

public int size(){
       int count = 0;
       ListNode cur = head;
       while (cur != null) {
           count++;
           cur = cur.next;
       }
       return count;
   }

 3.查询数据

public boolean contains(int key){
       ListNode cur = head;
       while (cur != null) {
           //如果val值 是引用类型  那么这里得用equals来进行比较！！！
           if(cur.val == key) {
               return true;
           }
           cur = cur.next;
       }
       return false;
   }

4.链表的清空

public void clear() {
       //将所有结点都置空，更为安全
       while (head != null) {
           ListNode headNext = head.next;
           head.next = null;
           head = headNext;
       }
   }

3.3四大基本功能      

3.3.1 、增加元素结点

1.头插法：将新增结点放在链表的头部。

public void addFirst(int data){
       ListNode node = new ListNode(data);
       node.next = head;
       head = node;
   }

2.尾插法：将新增结点直接连接在链表的尾部

public void addLast(int data){
       ListNode node = new ListNode(data);
       if(head == null) {
           head = node;
           return;
       }
       ListNode cur = head;
       while (cur.next != null) {
           cur = cur.next;
       }
       //cur 指向的节点就是尾巴节点
       cur.next = node;
   }

3.选择下标值，添加结点

public void addIndex(int index,int data){
       int len = size();
       //0、判断index位置的合法性
       if(index < 0 || index > len) {
           throw new IndexOutOfBounds("任意位置插入数据的时候，index位置不合法: "+index);
       }
       if(index == 0) {
           addFirst(data);
           return;
       }
       if(index == len) {
           addLast(data);
           return;
       }
       //1、先找到index-1位置的节点
       ListNode cur = findIndex(index);
       //2、进行插入
       ListNode node = new ListNode(data);
       node.next = cur.next;
       cur.next = node;
}

3.3.2.查找元素结点

查找一个元素，返回对应的下标值。

public ListNode findIndex(int index) {
       ListNode cur = head;
       while (index - 1 != 0) {
           cur = cur.next;
           index--;
       }
       return cur;//index-1位置的节点
   }

3.3.3.删除元素结点

先找到对应的下标值，然后进行删除。删除方法，前一个结点连接到删除结点的后一个结点。

 如图，先断开d2与d3的连接，然后d2直接连接d4

代码实现：

//删除第一次出现关键字为key的节点
   public void remove(int key){
       if(head == null) {
           return;
       }
       //当删除结点为头结点
       if(head.val == key) {
           head = head.next;
           return;
       }
       ListNode prev = searchPrev(key); //返回待删除结点的前一个结点
       if(prev == null) {
           System.out.println("没有这个数据！");
           return;
       }
       ListNode del = prev.next;
       prev.next = del.next;
   }
   private ListNode searchPrev(int key) {
       ListNode prev = head;
       while (prev.next != null) {
           if(prev.next.val == key) {
               return prev;
           }else {
               prev = prev.next;
           }
       }
       return null;
   }

3.3.4.结点信息修改

修改指定下标值的结点元素

public void searchPrev(int num,int date) {
       ListNode prev = head;
      for(int i=0;i<num-1;i++) {
               prev = prev.next;  
       }
       prev.val=date;
   }

四.LinkedList是什么？

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

 如图所示：1. LinkedList实现了List接口

                   2. LinkedList的底层使用了双向链表

                   3. LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问。

                  4. LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)

                   5. LinkedList比较适合任意位置插入的场景

五.LinkedList使用方法

来源：https://blog.csdn.net/m0_74097410/article/details/130320166