单链表的实现（单向无头不循环链表）+增删改查等功能

注意： * 如果想弄清楚单链表的原理，可以通过画图＋代码去理解。 * 我的单链表实现了11个功能，文章前面具体列出了每个方法的代码，以及详细的代码注释和个人解释。 * 如果只要整个源代码，可以直接到文章末尾。包含完整的单链表源代码和main函数测试代码，以及每个方法的测试结果。 * * 码字不易，也达不到深入理解，但都是经过测试可以运行的。如果有问题，欢迎提出，欢迎白嫖。

1. 实现链表中的单向无头不循环链表

单向指的是每个节点只有后继节点的引用。无头指的是，不含有头节点，也就是头节点不固定。在本次单链表实现中，为了方便打印，查找等功能，我们将会定义一个可变头节点不循环指的是，尾结点指向空，整个链表不构成一个环。

2. 单链表数据结构

每个单链表由n个节点构成。一个节点有两个域，一个data值域，用来存放当前节点的值。另外一个域是引用域，用来存放后继节点的引用。因此，我们可以定义一个节点类，其中包含基本数据类型data，以及后继节点的引用的引用类型next。 /** * Node节点类 */ class Node { public int data; public Node next; public Node(int data) { this.data = data; } } 单链表中包含许多方法，比如插入，删除，等等。我们为了方便方法，可以在单链表类开始，定义一个全局引用head。 //单链表的实现类 public class MySinglyLinkedList { //头节点 public Node head; } 单链表类中还有许多方法，接下来，将一一实现。

3.单链表实现增删改查等功能

1. 头插法：每次插入数据，都在链表的第一个位置。

/** * 头插法 * @param data */ public void addFirst(int data) { //将data数据变成一个节点类型 Node node = new Node(data); //欲要插入的节点的后继节点指向原来头节点 node.next = this.head; //头节点置为新的节点 this.head = node; }

2. 尾插法：每次插入的数据放在最后，即接在原来尾结点后面。

/** * 尾插法 * @param data */ public void addLast(int data) { Node node = new Node(data); //判断头节点是否为空 if (this.head == null) { this.head = node; return; } //初始化一个节点，并指向头节点 Node cur = this.head; //循环，找到尾结点 while (cur.next != null) { cur = cur.next; } //将尾结点的后继节点指向欲要插入节点 cur.next = node; //新插入节点成为新的尾结点，所以next域置为空 node.next =null; }

3. 打印链表：因为单链表有n个节点，所以用自己的打印方法，可以很方便的打印一个单链表。

/** * 打印单链表 */ public void display() { //初始化一个节点 Node cur = this.head; //循环，打印每一个节点的data域，即每个节点的值 while (cur != null) { System.out.print(cur.data+" "); cur = cur.next; } System.out.println(); }

4. 获取单链表长度：通过循环，从头节点移动到尾结点，每移动一个节点，计数变量count加一

/** * 获取单链表长度 * @return */ public int size() { //初始化一个int类，用来计数 int count = 0; Node cur = this.head; //循环，每移动一个节点，count加一 while (cur != null) { cur = cur.next; count++; } return count; }

5. 查找index号位置节点的前驱节点。头节点从0开始计算，查找某一个位置的前一个节点。

/** * 查找index号位置节点的前驱节点 * @param index * @return */ public Node searchPrevIndex(int index) { //判断位置是否合法，size（）方法调用的前面第4个写的求链表长度方法 if (index <= 0 || index >= size()) { return null; } Node prev = this.head; int count = 0; //循环，从0开始，小于index-1的位置，即index的前驱结点 while (count < index - 1) { prev = prev.next; count++; } //返回index的前驱结点 return prev; }

6. 任意位置插入：一个下标index，一个数据data。

/** * 任意位置插入，下标从0开始 * @param index * @param data */ public void addIndex(int index,int data) { //如果插入第一个，则直接调用前面写的头插法方法 if (index == 0) { addFirst(data); //如果插入位置等于单链表长度，即是尾插法，直接调用前面写的尾插方法 } else if (index == size()) { addLast(data); } else { //调用通过下标查找前驱节点的方法 Node cur = searchPrevIndex(index); Node node = new Node(data); //将要插入的节点的next域指向前驱节点的next域 node.next = cur.next; //前驱节点的next域指向新节点 cur.next = node; } }

7. 查找是否包含某个关键字key。

/** * 查找是否包含某个关键字 * @param key * @return */ public boolean contains(int key) { //判断头节点是否为空 if (this.head == null) { return false; } else { Node cur = this.head; //循环 while (cur != null) { //判断当前节点的data域是否等于key if (cur.data == key) { return true; } //cur节点后移一位 cur = cur.next; } return false; } }

8. 查找关键字key的前驱节点：通过查找单链表中是否含有关键字key，没有返回null，有则返回key节点的前驱节点。

/** * 查找关键字key的前驱 * @param key * @return */ public Node searchPrevKey(int key) { Node prev = this.head; //循环 while (prev.next != null) { //判断当前节点的下一个节点的data域是否等于关键字key if (prev.next.data == key) { return prev; } //当前节点后移一位 prev = prev.next; } return null; }

9. 删除第一次出现的关键字：只删除一次，没有关键字则不删除。

/** * 删除第一个出现的关键字key * @param key */ public void removeKey(int key) { //判断头节点是否为空 if (this.head == null) { return; } //调用前面写的，通过关键字key查找前驱节点的方法 Node del = searchPrevKey(key); //如果删除的节点的前驱节点为空，即删除单链表的头节点 if (del == null) { //直接将头节点指向头节点的下一个节点 this.head = this.head.next; //判断，如果删除节点的前驱节点，它的下一个的下一个节点为空，即删除尾结点 } else if (del.next.next == null) { //直接将删除节点的前驱节点的next域置为空 del.next = null; } else { //否则，删除节点的前驱节点，它的next指向前驱节点的下一个的下一个 del.next = del.next.next; } }

10. 删除单链表中，所有关键字为key的节点。此方法不用循环调用前面删除一个关键字的方法，而是遍历单链表一次，删除所有关键字节点。

首先定义一个无用节点，值随便给，让它指向头节点。然后从这个节点的下一个节点开始判断，这样可以方便的解决，需要删除头节点关键字而带来的麻烦。 /** * 删除所有关键字为key * @param key */ public void removeKeyAll(int key) { //判断头节点 if (this.head == null) { return; } //初始化一个无用的头节点 Node myHead = new Node(-1); //再定义一个节点用来保存自己初始化的无用节点，后面会用到 Node temp = myHead; //让这个无用节点的next域指向头节点 myHead.next = this.head; //循环 while (myHead.next != null) { //从无用节点的下一个节点的data域判断是否等于关键字 if (myHead.next.data == key) { //判断，如果当前节点的下一个节点的下一个next指向null，即代表将要删除尾结点 if (myHead.next.next == null) { //直接将当前节点额next域置为空 myHead.next = null; //并返回，因为最后一个节点都遍历完了，不再需要执行下面代码 return; } else { //否则，即删除的不是尾结点且不等于关键字，那么后移 myHead.next = myHead.next.next; } } //无用节点后移 myHead = myHead.next; } //因为无用节点和头节点都乱了，所以欲要重置head，指向刚刚保存无用节点的下一个节点 this.head = temp.next; }

11. 清空链表。如果直接将头节点置为空，那么头节点后面的节点的next域还有指向关系，这些存在指向关系的节点，因为我们不知道他们的引用（因为我们已经把头节点的引用置为空了），而引用又不为空，所以JVM不会自动回收。就会造成内存泄露。为此，我们必须利用循环，将每一个节点的next域都置为空，这样才会被系统自动回收。

/** * 清空单链表，防止内存泄漏 * 将单链表每个next都置为空 */ public void clear() { //循环，将每一个节点的next域都置为空 while (this.head != null) { Node cur = this.head.next; this.head = null; this.head = cur; } }

4. 完整源代码

单链表类（包含单链表的方法+节点Node类） package day9_10_20; /** * @author：fover * @version：1.0 * @function：单链表的实现 */ public class MySinglyLinkedList { //头节点 public Node head; /** * 头插法 * @param data */ public void addFirst(int data) { //将data数据变成一个节点类型 Node node = new Node(data); /* * 可以不判断头节点是否为空 if (head == null) { head = node; return; } */ //欲要插入的节点的后继节点指向原来头节点 node.next = this.head; //头节点置为新的节点 this.head = node; } /** * 尾插法 * @param data */ public void addLast(int data) { Node node = new Node(data); //判断头节点是否为空 if (this.head == null) { this.head = node; return; } //初始化一个节点，并指向头节点 Node cur = this.head; //循环，找到尾结点 while (cur.next != null) { cur = cur.next; } //将尾结点的后继节点指向欲要插入节点 cur.next = node; //新插入节点成为新的尾结点，所以next域置为空 node.next =null; } /** * 任意位置插入，下标从0开始 * @param index * @param data */ public void addIndex(int index,int data) { //如果插入第一个，则直接调用前面写的头插法方法 if (index == 0) { addFirst(data); //如果插入位置等于单链表长度，即是尾插法，直接调用前面写的尾插方法 } else if (index == size()) { addLast(data); } else { //调用通过下标查找前驱节点的方法 Node cur = searchPrevIndex(index); Node node = new Node(data); //将要插入的节点的next域指向前驱节点的next域 node.next = cur.next; //前驱节点的next域指向新节点 cur.next = node; } } /** * 打印单链表 */ public void display() { //初始化一个节点 Node cur = this.head; //循环，打印每一个节点的data域，即每个节点的值 while (cur != null) { System.out.print(cur.data+" "); cur = cur.next; } System.out.println(); } /** * 获取单链表长度 * @return */ public int size() { //初始化一个int类，用来计数 int count = 0; Node cur = this.head; //循环，每移动一个节点，count加一 while (cur != null) { cur = cur.next; count++; } return count; } /** * 查找index号位置节点的前驱节点 * @param index * @return */ public Node searchPrevIndex(int index) { //判断位置是否合法，size（）方法调用的前面第4个写的求链表长度方法 if (index <= 0 || index >= size()) { return null; } Node prev = this.head; int count = 0; //循环，从0开始，小于index-1的位置，即index的前驱结点 while (count < index - 1) { prev = prev.next; count++; } //返回index的前驱结点 return prev; } /** * 查找关键字key的前驱 * @param key * @return */ public Node searchPrevKey(int key) { Node prev = this.head; //循环 while (prev.next != null) { //判断当前节点的下一个节点的data域是否等于关键字key if (prev.next.data == key) { return prev; } //当前节点后移一位 prev = prev.next; } return null; } /** * 查找是否包含某个关键字 * @param key * @return */ public boolean contains(int key) { //判断头节点是否为空 if (this.head == null) { return false; } else { Node cur = this.head; //循环 while (cur != null) { //判断当前节点的data域是否等于key if (cur.data == key) { return true; } //cur节点后移一位 cur = cur.next; } return false; } } /** * 删除第一个出现的关键字key * @param key */ public void removeKey(int key) { //判断头节点是否为空 if (this.head == null) { return; } //调用前面写的，通过关键字key查找前驱节点的方法 Node del = searchPrevKey(key); //如果删除的节点的前驱节点为空，即删除单链表的头节点 if (del == null) { //直接将头节点指向头节点的下一个节点 this.head = this.head.next; //判断，如果删除节点的前驱节点，它的下一个的下一个节点为空，即删除尾结点 } else if (del.next.next == null) { //直接将删除节点的前驱节点的next域置为空 del.next = null; } else { //否则，删除节点的前驱节点，它的next指向前驱节点的下一个的下一个 del.next = del.next.next; } } /** * 删除所有关键字为key * @param key */ public void removeKeyAll(int key) { //判断头节点 if (this.head == null) { return; } //初始化一个无用的头节点 Node myHead = new Node(-1); //再定义一个节点用来保存自己初始化的无用节点，后面会用到 Node temp = myHead; //让这个无用节点的next域指向头节点 myHead.next = this.head; //循环 while (myHead.next != null) { //从无用节点的下一个节点的data域判断是否等于关键字 if (myHead.next.data == key) { //判断，如果当前节点的下一个节点的下一个next指向null，即代表将要删除尾结点 if (myHead.next.next == null) { //直接将当前节点额next域置为空 myHead.next = null; //并返回，因为最后一个节点都遍历完了，不再需要执行下面代码 return; } else { //否则，即删除的不是尾结点且不等于关键字，那么后移 myHead.next = myHead.next.next; } } //无用节点后移 myHead = myHead.next; } //因为无用节点和头节点都乱了，所以欲要重置head，指向刚刚保存无用节点的下一个节点 this.head = temp.next; } /** * 清空单链表，防止内存泄漏 * 将单链表每个next都置为空 */ public void clear() { //循环，将每一个节点的next域都置为空 while (this.head != null) { Node cur = this.head.next; this.head = null; this.head = cur; } } } /** * Node节点类 */ class Node { public int data; public Node next; public Node(int data) { this.data = data; } } main方法测试类 package day9_10_20; import org.w3c.dom.Node; /** * @author：fover * @date：2020/10/20 10:31 * @version：1.0 * @function：单链表测试 */ public class MySinglyLinkedListTest { public static void main(String[] args) { MySinglyLinkedList myList = new MySinglyLinkedList(); System.out.println("1、头插法1,2,3,4,5测试："); myList.addFirst(1); myList.addFirst(2); myList.addFirst(3); myList.addFirst(4); myList.addFirst(5); myList.display(); System.out.println("2、打印测试："); myList.display(); System.out.println("3、尾插法6,7,8,9,10测试："); myList.addLast(6); myList.addLast(7); myList.addLast(8); myList.addLast(9); myList.addLast(10); myList.display(); System.out.println("4、查找3号位置前驱节点测试："); System.out.println(myList.searchPrevIndex(3).data); System.out.println("5、获取单链表长度测试："); System.out.println(myList.size()); System.out.println("6、在10号位置插入元素99测试："); myList.addIndex(10,99); myList.display(); System.out.println("7、是否包含关键字99测试："); System.out.println(myList.contains(99)); System.out.println("8、查找关键字99的前驱测试："); System.out.println(myList.searchPrevKey(99).data); System.out.println("9、删除第一个出现的关键字99测试："); myList.removeKey(99); myList.display(); System.out.println("10、删除所有关键字8测试："); myList.addIndex(4,8); myList.addIndex(1,8); myList.addIndex(0,8); System.out.print("删除前："); myList.display(); System.out.print("删除后："); myList.removeKeyAll(8); myList.display(); System.out.println("11、清空单链表测试(防止内存泄露)："); myList.clear(); myList.display(); System.out.println("-----------结束------------"); } } 测试结果展示

欢迎白嫖，感谢提出问题^ - ^