入门数据结构JAVA DS——如何实现简易的单链表(用JAVA实现)

前言

链表（Linked List）是一种线性数据结构，它由一系列节点组成，每个节点包含两个部分：存储数据的部分和指向下一个节点的指针（或引用）。链表的结构使得它能够动态地增长和收缩，适合在不固定长度的序列中进行插入和删除操作。

链表的基本概念：

节点（Node）：链表的基本单位，每个节点包含两个部分：
- 数据域（Data）：存储节点的具体数据。
- 指针域（Pointer/Next）：存储指向下一个节点的引用。
头节点（Head）：链表的第一个节点，通常用于存储链表的入口。
尾节点（Tail）：链表的最后一个节点，它的指针域指向 null（在 Java 等语言中）或 None（在 Python 中），表示链表的结束。
空链表：当链表中没有任何节点时，它被称为空链表，头节点指向 null。

并且,相比于顺序表,链表可以动态的管理大小,在插入或者删除元素时,时间复杂度也更低.

以一言蔽之:

链表在需要动态内存管理、频繁插入删除操作、不确定数据量的场景中优势明显.

那么,我们怎么徒手搓出来一个链表呢? 本文以单向链表为例

如何创建链表中的节点

为了从零开始写出一个链表,我们可以大致分成两个步骤

第一:我们首先要能写出一个节点

第二:我们把这些节点以某种方式连接起来

那我们首先做到第一步,怎么创建一个节点?

很显然,这个节点需要一个值域和一个地址域,前者存储它的值,后者存储下一个节点的地址,

这样就创造了将节点们连接起来的条件

我们只需要创建一个类

public class Listnode
{public int value;public Listnode next;public Listnode(int value){this.value = value;}
}

就正如代码所写的,其中value表示值, next 说人话就是下一个节点的地址.

说的官方一点就是:它表示一个指向链表中下一个节点的引用.

链表的实现

为了实现无头单向非循环链表

我们需要如下的一些方法(里面不但存在基本方法,也存在笔者的私货)

       public void addFirst(int data);//尾插法public void addLast(int data);//任意位置插入,第一个数据节点为0号下标public void addIndex(int index,int data);//查找是否包含关键字key是否在单链表当中public boolean contains(int key);//删除第一次出现关键字为key的节点public void remove(int key);//删除所有值为key的节点public void removeAllKey(int key);//得到单链表的长度public int size();public void clear();public void reverseList();// 反转链表public void display() ;

我们可以把它们写进一个接口里

OK,现在我们再写一个类,来正式地实现我们这些方法吧

在实现类中,我们首先要定义好头节点,和使用大小这两个值.

public  class MyIlist implements IList
{public int usedsize;public Listnode head;
}

头插法

就是往链表的头部插入新的元素,这里肯定有两种情况

情况一: 链表为空,那么这个插入的节点就是头结点

情况二:链表不为空,那么我们就要改变原头结点的位置,具体实现如下

新的结点node的地址域中的值就是原来的头结点的地址

然后node结点变成新的节点

代码如下

    @Overridepublic void addFirst(int data) {Listnode node = new Listnode(data);if (head == null) {this.head = node;} else {node.next = this.head;this.head = node;}}

尾插法

往链表的最末端插入新的元素,思路同样很简单,找到末端的结点,它的地址域肯定是null.

然后将它的地址域的值设为新节点的地址

代码如下:

    @Overridepublic void addLast(int data){Listnode node = new Listnode(data);if (head == null) {this.head = node;return;}Listnode cur = this.head;while (cur.next != null) {cur = cur.next;}cur.next = node;}

删除一个值为key的结点

这个相对来说比较麻烦,但是思路很简单,你需要删除那个,你就直接"跳过"它,即将它上一个结点的地址域设置为它的下一个结点的地址

(图很丑,但是能理解意思就好)

为了达到这个目的,我们首先就要找到需要删掉结点的上一个结点

方法如下:

    private Listnode findIndex2(int key) {Listnode cur = this.head;while (cur.next != null) {if (cur.next.value == key) {return cur;}cur = cur.next;}return null;}

但这也漏洞啊,头结点怎么办?头结点也没有前置结点啊?

所以这就是特例,如果是要删的是头结点,就直接让 head=head.next 即可

完整代码如下:

    @Overridepublic void remove(int key) {if (this.head == null) {return;}if (this.head.value == key) {this.head = this.head.next;return;}Listnode cur = findIndex2(key);if (cur == null) {return;}Listnode del = cur.next;// del结点就是要删除的结点cur.next = del.next;// 这步是什么就不用我多说了吧}

删除所有值为key的结点

这个呢其实和删除单一结点差不多,只不过是要重复多遍

这里笔者就给一个简洁的概况一切情况的代码

    @Overridepublic void removeAllKey(int key){Listnode dummy = new Listnode(0);dummy.next = this.head;Listnode cur = dummy;while (cur.next != null) {if (cur.next.value == key) {cur.next = cur.next.next;} else {cur = cur.next;}}this.head = dummy.next;}

在指定下标插入元素

该方法同样思路简单,找到前一个下标的结点

将它的地址域的值赋给需要插入的node的地址域,然后改变前一个下标结点的地址域

    private Listnode findIndex(int idx) {Listnode cur = this.head;int num = 0;while (num != idx - 1) {cur = cur.next;num++;}return cur;}@Overridepublic void addIndex(int index, int data) {if (index < 0 || index > size()) {return;}if (index == 0) {addFirst(data);return;}if (index == size()) {addLast(data);return;}Listnode cur = findIndex(index);Listnode node = new Listnode(data);node.next = cur.next;cur.next = node;}

其他方法

剩下的就是一些其他的方法,比如求链表的大小,求链表是否有值为X的结点,清除链表中的所有元素,按顺序打印链表元素等

笔者在此一并展示

    @Overridepublic int size() {Listnode cur = this.head;this.usedsize = 0;while (cur != null) {usedsize++;cur = cur.next;}return usedsize;}

    @Overridepublic void clear() {Listnode cur = this.head;while (cur != null) {Listnode curNext = cur.next;cur.value = 0;cur.next = null;cur = curNext;}head = null;System.out.println("清空");}

   @Overridepublic boolean contains(int key) {Listnode cur = this.head;while (cur != null) {if (cur.value == key) {return true;}cur = cur.next;}return false;}

    @Overridepublic void display() {Listnode cur = this.head;if (head == null) {System.out.println("链表为空");return;}while (cur != null) {System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}