Java数据结构与算法--链表(Linked List)
【摘要】 链表在许多场景中发挥着重要作用，特别是当需要频繁进行插入和删除操作，且对随机访问要求不高时，链表是一种非常合适的数据结构选择。下面主要介绍的是单链表：
深入了解链表：
链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的链接（指针），但是在Java中没有指针这个说法，我们称其为引用。
链表的主要特点包括：
-
动态性
- 可以在运行时方便地添加或删除节点，无需事先确定链表的大小。
- 例如，在需要不断添加新用户信息的场景中，链表能够灵活适应数据量的变化。
-
内存分配
- 节点在内存中可以不连续存储，这与数组不同。
- 使得链表能够更有效地利用内存空间。
链表分为多种类型，常见的有：
1.单链表
- 每个节点只有一个指向下一个节点的指针。
- 从头到尾进行遍历。
- 例如，实现一个简单的任务队列，新任务添加到链表尾部，处理任务从头部开始。
2.双向链表
- 节点既有指向前一个节点的指针，也有指向下一个节点的指针。
- 可以双向遍历，在查找特定节点时可能更高效。
3.循环链表
- 尾节点的指针指向头节点，形成一个环。
链表的操作主要包括：
1.插入节点
- 可以在头部、尾部或中间位置插入。
2.删除节点
- 根据特定条件删除指定节点。
3.查找节点
- 通常需要从链表的头部或尾部开始逐个遍历。
链表的一些缺点：
1.访问效率低
- 要访问特定位置的节点，需要从头开始遍历，时间复杂度较高。
2.额外的指针存储空间
- 每个节点都需要存储指针，增加了存储开销。
总之，链表在许多场景中发挥着重要作用，特别是当需要频繁进行插入和删除操作，且对随机访问要求不高时，链表是一种非常合适的数据结构选择。下面主要介绍的是单链表：
链表的节点类设计：
这里采用私密的静态类方法定义Node，由于不知道element是什么类型，这里照样使用泛型，代码实现如下：
private static class Node<E> {
private E e;
private Node<E> next;
public Node(E e) {
this.e = e;
}
}定义一个链表对象：
public class LinkedList<E> {
private Node<E> head = new Node<>(null) ;
private int size;链表的添加方法：
在指定位置(index)处插入一个结点(node)，只需要两步即可：
- 可以先修改插入的结点的后继结点（也就是下一个结点）指向，指向原本在这个位置的结点：
- 接着我们可以将前驱结点（也就是上一个结点）的后继结点指向修改为我们新插入的结点：
这样，我们就成功的插入了一个新的结点，现在新插入的结点到达了原本的第二个位置上：
按照这个思路，我们只需要找到index指向的这个节点，即可完成插入，代码实现如下：
public class LinkedList<E> {
private Node<E> head = new Node<>(null); // 初始化头节点，值为 null
private int size; // 记录链表中元素的数量
/**
* 在指定索引处添加元素
* @param e 要添加的元素
* @param index 元素要添加的索引位置
*/
public void add(E e, int index) {
if (index < 0 || index > size) throw new IndexOutOfBoundsException(); // 检查索引是否越界，越界则抛出异常
Node<E> prev = head; // 从头部开始
for (int i = 0; i < index; i++) { // 找到指定索引位置的前一个节点
prev = prev.next;
}
Node<E> node = new Node<>(e); // 创建新节点
node.next = prev.next; // 新节点的 next 指向原索引位置的节点
prev.next = node; // 前一个节点的 next 指向新节点
size++; // 链表元素数量加 1
}
}链表的删除方法：
插入操作完成之后，我们接着来看删除操作，删除操作就更简单了，可以直接将待删除的结点的前驱结点指向修改为待删除节点的下一个：
这样，理论上来说，待删除结点就已经不在链表中了，所以我们只需要释放掉结点所占用的内存空间（JVM会自动回收）就可以了：
代码实现：
public E remove(int index) {
if (index <0 || index > size-1) throw new IndexOutOfBoundsException();
Node<E> prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;}
E e = prev.next.e;
prev.next = prev.next.next;
return e;
}链表的get方法：
要像列表一样访问指定的index下标的元素，在单链表中只能一个一个往后找(时间复杂度O(n))，会比顺序表(O(1))复杂度高很多。代码实现：
public E get(int index) {
if (index <0 || index > size-1) throw new IndexOutOfBoundsException();
Node<E> node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node.e;
}
public int size() {
return size;
}链表的转字符串输出方法：
链表本身不能直接输出，要想以特定的方式输出一个链表，就需要去定义一个toString方法，下面是一个简单的代码示例：
完整代码实现单链表：
import org.w3c.dom.Node;
public class LinkedList<E> {
private Node<E> head = new Node<>(null) ;
private int size;
public void add(E e,int index) {
if (index <0 || index > size) throw new IndexOutOfBoundsException();
Node<E> prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node<E> node = new Node<>(e);
node.next = prev.next;
prev.next = node;
size++;
}
private static class Node<E> {
private E e;
private Node<E> next;
public Node(E e) {
this.e = e;
}
}
public E remove(int index) {
if (index <0 || index > size-1) throw new IndexOutOfBoundsException();
Node<E> prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;}
E e = prev.next.e;
prev.next = prev.next.next;
return e;
}
public E get(int index) {
if (index <0 || index > size-1) throw new IndexOutOfBoundsException();
Node<E> node = head;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node.e;
}
public int size() {
return size;
}
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> node = head.next;
while (node != null) {
sb.append(node.e).append(" ");
node = node.next;
}
return sb.toString();
}
}
“戒除欲望，控制行为，充实生活，美好的世界。”——《yuanziyu》
【版权声明】本文为华为云社区用户原创内容，未经允许不得转载，如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）