查看: 5026|回复: 0

【Java演示】什么是链表？数据结构

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2020-5-4 15:55 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

【Java演示】什么是链表？数据结构
一、单向链表

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。
单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。
链表的第1个节点被称为头节点，最后1个节点被称为尾节点，尾节点的next指针指向空。

什么叫随机存储呢？

如果说数组在内存中的存储方式是顺序存储，那么链表在内存中的存储方式则是随机存储。
上一节我们讲解了数组的内存分配方式，数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式，链表的每一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。

图中的箭头代表链表节点的next指针。

链表的基本操作1. 查找节点

在查找元素时，链表不像数组那样可以通过下标快速进行定位，只能从头节点开始向后一个一个节点逐一查找。

/**
   * 链表查找元素
   *
   * @param index 查找的位置
   * @return index位置的Node对象
   */
public Node get(int index) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表的节点的范围！");
      }
      Node temp = head;
      for (int i = 0; i < index; i++) {
         temp = temp.next;
      }
      return temp;
}

链表中的数据只能按顺序进行访问，最坏的时间复杂度是O(n)

2. 更新节点

如果不考虑查找节点的过程，链表的更新过程会像数组那样简单，直接把旧数据替换成新数据即可。
如果不考虑查找元素的过程，只考虑纯粹的更新节点操作，时间复杂度是O(1)
/**
   * 更新节点将列表中指定位置的节点的data替换为指定的data。
   *
   * @param index 需要更新的节点的位置
   * @param data  新data
   * @return 旧data
   */
public int set(int index, int data) {
      Node x = get(index);
      int oldVal = x.data;
      x.data = data;
      return oldVal;
}

3. 插入节点

只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题。

与数组类似，链表插入节点时，同样分为3种情况。

尾部插入
头部插入
中间插入7 X0 L8 ]9 J& K

3.1. 尾部插入

尾部插入，是最简单的情况，把最后一个节点的next指针指向新插入的节点即可。

3.2. 头部插入

头部插入，可以分成两个步骤。

第1步，把新节点的next指针指向原先的头节点。
第2步，把新节点变为链表的头节点。' m1 A7 K% G' p

3.3. 中间插入

中间插入，同样分为两个步骤。

第1步，新节点的next指针，指向插入位置的节点。
第2步，插入位置前置节点的next指针，指向新节点。
6 a# \2 e$ o7 Z' |& O

三钟情况的代码合到一起

/**
   * 链表插入元素
   *
   * @param index 插入位置
   * @param data  插入元素被插入的链表节点的数据
   */
public void insert(int index, int data) {
      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 prvNode = get(index - 1);
         insertedNode.next = prvNode.next;
         prvNode.next = insertedNode;
      }
      size++;
}

/**
   * 链表插入元素
   *
   * @param index 插入位置
   * @param data  插入元素被插入的链表节点的数据
   */
public void insert(int index, int data) {
      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 prvNode = get(index - 1);
         insertedNode.next = prvNode.next;
         prvNode.next = insertedNode;
      }
      size++;
}
4. 删除元素

链表的删除操作同样分为3种情况。

尾部删除
头部删除
中间删除
4 A# Y/ C0 T/ {/ \5 `6 R H

4.1. 尾部删除

尾部删除，是最简单的情况，把倒数第2个节点的next指针指向空即3 }) Q- P+ d. i- E. ^$ o) M
可。

4.1. 头部删除

头部删除，也很简单，把链表的头节点设为原先头节点的next指针即可。

4.1. 中间删除

中间删除，同样很简单，把要删除节点的前置节点的next指针，指向要# d5 y6 n$ @ _, C2 D% _8 z
删除元素的下一个节点即可。

这里需要注意的是，许多高级语言，如Java，拥有自动化的垃圾回收机制，所以我们不用刻意去释放被删除的节点，只要没有外部引用指向它们，被删除的节点会被自动回收。
如果不考虑插入、删除操作之前查找元素的过程，只考虑纯粹的插入和删除操作，时间复杂度都是O(1)
/**
   * 链表删除元素
   *
   * @param index 删除的位置
   * @return 被删除的节点
   */
public Node remove(int index) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表节点范围");
      }
      Node removeNode;
      if (index == 0) {
         if (size == 0) {
            throw new NullPointerException("当前链表为空，不可以进行删除操作");
         }
         //删除头节点
         removeNode = head;
         head = head.next;
      } else if (index == size - 1) {
         //删除尾节点
         Node preNode = get(index - 1);
         removeNode = preNode.next;
         preNode.next = null;
         last = preNode;
      } else {
         //删除中间节点
         Node prevNode = get(index - 1);
         removeNode = prevNode.next;
         prevNode.next = prevNode.next.next;
      }
      size--;
      return removeNode;
}
Java实现链表的完整代码package chapter2.part2;

/**
* Created by IntelliJ IDEA.
*
* @Author: 张志浩  Zhang Zhihao
* @Email: 3382885270@qq.com
* @Date: 2020/5/3
* @Time: 13:39
* @Version: 1.0
*/
public class MyLinkedList2 {
private Node head; //头节点
private Node last; //尾节点
private int size; //链表实际长度

public static void main(String[] args) {
      MyLinkedList2 myLinkedList = new MyLinkedList2();
//       myLinkedList.remove(0); // java.lang.NullPointerException: 当前链表为空，不可以进行删除操作
//       myLinkedList.remove(3); // java.lang.IndexOutOfBoundsException: 超出链表节点范围
      myLinkedList.insert(0, 3);
      myLinkedList.insert(1, 7);
      myLinkedList.insert(2, 9);
      myLinkedList.insert(3, 5);
      myLinkedList.insert(1, 6);
      myLinkedList.remove(0);
      myLinkedList.set(0, 23);
      myLinkedList.output();
}

/**
   * 链表插入元素
   *
   * @param index 插入位置
   * @param data  插入元素被插入的链表节点的数据
   */
public void insert(int index, int data) {
      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 prvNode = get(index - 1);
         insertedNode.next = prvNode.next;
         prvNode.next = insertedNode;
      }
      size++;
}

/**
   * 链表删除元素
   *
   * @param index 删除的位置
   * @return 被删除的节点
   */
public Node remove(int index) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表节点范围");
      }
      Node removeNode;
      if (index == 0) {
         if (size == 0) {
            throw new NullPointerException("当前链表为空，不可以进行删除操作");
         }
         //删除头节点
         removeNode = head;
         head = head.next;
      } else if (index == size - 1) {
         //删除尾节点
         Node preNode = get(index - 1);
         removeNode = preNode.next;
         preNode.next = null;
         last = preNode;
      } else {
         //删除中间节点
         Node prevNode = get(index - 1);
         removeNode = prevNode.next;
         prevNode.next = prevNode.next.next;
      }
      size--;
      return removeNode;
}

/**
   * 更新节点将列表中指定位置的节点的data替换为指定的data。
   *
   * @param index 需要更新的节点的位置
   * @param data  新data
   * @return 旧data
   */
public int set(int index, int data) {
      Node x = get(index);
      int oldVal = x.data;
      x.data = data;
      return oldVal;
}

/**
   * 链表查找元素
   *
   * @param index 查找的位置
   * @return index位置的Node对象
   */
public Node get(int index) {
      if (index < 0 || index > size) {
         throw new IndexOutOfBoundsException("超出链表的节点的范围！");
      }
      Node temp = head;
      for (int i = 0; i < index; i++) {
         temp = temp.next;
      }
      return temp;
}

/**
   * 输出链表
   */
public void output() {
      Node temp = head;
      while (temp != null) {
         System.out.print(temp.data + " ");
         temp = temp.next;
      }
}

/**
   * 链表节点
   */
class Node {
      int data;
      Node next;

      Node(int data) {
         this.data = data;
      }
}
}

二、双向链表

双向链表比单向链表稍微复杂一些，它的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev 指针。

————————————————
版权声明：本文为CSDN博主「爱做梦的鱼」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43124279/article/details/105904468

2.png (256.36 KB, 下载次数: 243)