Java数据结构基础丨链表

首页
/ 默认分类 / 正文

链表的基本知识

  • 链表对应的英文名称是 Linked List，是一种物理存储单元上非连续、非顺序的数据结构，由若干个节点(node)组成。每个结点包括两个部分：一个是存储数据元素的数据域(data)，另一个是存储下一个结点地址的指针域(next)。
  • 链表的第一个节点被称为头结点，最后一个节点被称为尾结点，尾结点的next指针指向一个空地址 NULL。
  • 链表有很多种不同的类型：单向链表，双向链表以及循环链表......

  • 不同于数组的顺序存储，链表在内存中是随机存储。

    // 链表节点,变量data存放数据，指针next指向下一个节点
 private static class Node{
     int data;
     Node next;
     Node(int data){
         this.data = data;
     }
 }

    链表的基本操作

    • 查找——时间复杂度：O(n)

      /**
* 链表操作：查找元素
* @param index 查找的位置
**/
 public Node get(int index)throws Exception{
if (index < 0 || index >= size){
    throw new IndexOutOfBoundsException("超出链表节点实际范围！");
}
Node temp = head;
for(int i = 0; i < index; i++){
   temp = temp.next;
}
return temp;
 }
    • 插入——时间复杂度：O(1)
    /**
 * 链表操作：插入元素
 * @param data 插入的元素
 * @param index 插入的位置
 * */
public void insert(int data, int index)throws Exception{
    if (index<0 || index>size){
        throw new IndexOutOfBoundsException("超出链表节点实际范围！！！");
    }
    Node insertedNode = new Node(data);
    if (size == 0){
        //空链表
        head = insertedNode;
        last = insertedNode;
    }else if (index == 0){
        //插入头部
        insertedNode.next = head;
        head = insertedNode;
    }else if (size == index){
        //插入尾部
        last.next = insertedNode;
        last = insertedNode;
    }else{
        //插入中间
        Node prevNode = get(index-1);
        //将新结点的 next指针指向原来旧结点的 next指针指向的内存地址
        insertedNode.next = prevNode.next;
        //将原来旧结点的 next指针指向新结点的内存地址
        prevNode.next = insertedNode;
    }
    size++;
}

    • 删除——时间复杂度：O(1)

      /**
* 链表操作：删除元素
* @param index 删除的位置
**/
 public Node remove(int index)throws Exception{
  if (index<0 || index>=size){
      throw new IndexOutOfBoundsException("超出链表节点实际范围！！！");
  }
  Node removedNode = null;
  if (index == 0){
      //删除头部节点
      removedNode = head;
      head = head.next;
  }else if (index == size-1){
      //删除尾部节点
      Node prevNode = get(index-1);
      removedNode = prevNode.next;
      prevNode.next = null;
      last = prevNode;
  }else {
      //删除中间节点
      Node prevNode = get(index-1);
      Node nextNode = prevNode.next.next;
      removedNode = prevNode.next;
      //即 a>>b>>c，删除 b，只需要将 c赋值给 a.next即可
      prevNode.next = nextNode;
  }
  size--;
  return removedNode;
 }

    单向链表的应用场景

  • 撤销和回退功能。
  • 实现LRU缓存淘汰算法。
  • 判断某个字符串是否为回文字符串。
  • 实现图、HashMap等一些高级数据结构。
  • ...

循环链表

可以说，循环链表是一种特殊的单链表。它与单链表的唯一区别在于尾结点，循环链表的尾结点指针指向链表的头结点。当要处理的数据具有环形结构特点时，特别适合采用循环链表。例如，约瑟夫问题。

循环链表的实现

public class CircleLinkedList {
    //指向循环链表的第一个结点
    private Node head;
    // 循环链表的长度
    private int length;
    public CircleLinkedList() {
        head = null;
        length = 0;
    }
    public Node getHead() {
        return head;
    }
    public int getLength() {
        return length;
    }

    /**
     * 尾部插入
     * @param newNode
     */
    public void insert(Node newNode) {
        if (head == null) {
            // 循环链表为空时，head 指向新的节点
            head = newNode;
        } else {
            Node temp = head;
            // 找到循环链表最后一个节点
            while (temp.next != head) {
                temp = temp.next;
            }
            // 插入新的节点
            temp.next = newNode;
        }
        // 循环链表新的结点指向 NULL
        newNode.next = head;
        // 循环链表长度加 1
        length++;
    }

    /**
     * 将新的结点插入到指定结点后
     * @param preNode 指定节点
     * @param newNode 新的节点
     */
    public void insert(Node preNode, Node newNode) {
        newNode.next = preNode.next;
        preNode.next = newNode;
        length++;
    }

    /**
     * 删除数据域为指定值的元素
     * @param e
     */
    public void del(int e) {
        Node temp = head;
        while (length >= 0) {
            // 找到数据域为 e 的结点
            if (temp.data == e) {
                if (temp.next == head) {
                    // 第一个节点
                    head = null;
                } else {
                    // 最后一个节点
                    temp.next = temp.next.next;
                }
                // 循环链表长度减 1
                length--;
                return;
            }
            // 找到下一个结点
            temp = temp.next;
        }
    }

    /**
     * 给定被删除元素的前一个结点，删除指定元素
     * @param preNode
     */
    public Node del(Node preNode) {
        Node delNode = preNode.next;
        if (delNode == head) {
            // 维护 head 的指向
            head = head.next;
        }
        // 删除
        preNode.next = preNode.next.next;
        length--;
        return delNode;
    }

    /**
     * 随机访问第 k 个结点
     * @param k
     * @return
     */
    public Node find(int k) {
        if (k <= 0) {
            throw new RuntimeException("输入的参数 k 必须大于 0");
        }
        int cnt = 1;
        Node temp = head;
        // 找到第 k 个元素
        while (cnt != k) {
            temp = temp.next;
            cnt++;
        }
        return temp;
    }

    /**
     * 打印循环链表所有有效节点
     * @return
     */
    public String printCircleLinkedList() {
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        Node temp = head;
        while (head != null && cnt < getLength()) {
            sb.append(temp.data);
            sb.append(" -> ");
            temp = temp.next;
            cnt++;
        }
        sb.append(", length = ");
        sb.append(length);
        return sb.toString();
    }
}
掘金

循环链表的应用场景

  1. 约瑟夫问题。
  2. 操作系统的分时问题。
  3. 键盘的缓冲，网络收发数据包的缓冲。
  4. ...

双向链表

双向链表它的每一个节点除了有数据(data)、后继指针(next)，还有前驱指针(prev)——指向前一个节点的指针。由于多了一个前驱指针,所以双向链表要更占内存，但它的效率更高,也更加实用（支持双向遍历），可以说是“空间换时间”了。
删除情况：

  1. 删除节点中含有特定值的节点；
  2. 删除给定指针指向的节点。

对于第1种情况，无论是单向链表还是双向链表，都需要从头节点开始遍历查找，查找到后，再执行删除操作。
对于第2种情况，因为双向链表中拥有前驱指针，只需要O(1)的时间复杂度；而单向链表为了找到前驱节点需要遍历，则需要O(n)。同理，对于“在某个指定节点前插入一个节点”这种情况，双向链表也是O(1)，单向链表也是O(n)。除此之外，对于一个有序链表，双向链表的按值查询的效率也比单向链表高一些。

双向循环链表

“缝合怪”：循环链表+双向链表（双向链表首尾相接）。

链表的优劣

  • 相较于数组，链表的内存空间消耗更大，用于储存结点指针信息。
  • 链表可以克服数组需要预先知道数据大小的缺点，充分利用计算机内存空间，实现灵活的内存动态管理。但是（单向）链表失去了数组根据下标随机读取的优点，想要找到某节点Z只能通过前一个节点Y的next指针来寻找，而想要找到节点 Y，又必须通过Y节点的前一个节点X的next指针来寻找...要找一个某一节点，必须要从头开始遍历，十分麻烦。链表的随机访问的性能没有数组好，需要O(n)的时间复杂度。
  • 数组在进行插入、删除操作时，为了保持内存数据的连续性，需要搬移大量数据，所以时间复杂度为O(n)；而由于不必须按顺序存储，链表在纯粹的插入、删除操作的时候可以达到O(1)；而如果考虑插入、删除操作之前需要遍历查找到元素，那么删除“特定值”操作也需要O(n)。
  • 由于链表的每个结点在内存里都是随机分布的，只是通过指针联系在一起，所以这些结点的地址并不相邻，无法利用 程序的局部性原理 来提前加载到缓存中来提升程序性能。所以，链表的查找、读取性能不及数组。如果数据以查找为主，很少涉及到增加和删除操作，那么选择数组，如果涉及到频繁的插入和删除，或元素所需分配空间过大，那么倾向于选择链表。

拓展

帅地玩编程-反转链表
码农有道-LRU缓存
掘金-链表练习
数据结构
版权属于：New
本文链接：https://newabug.top/archives/2.html
作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
打赏
Java数据结构基础丨数组
« 上一篇
Java数据结构基础丨队列
下一篇 »
评论区
头像
文章目录