Java实现单向链表

✅作者简介：热爱Java后端开发的一名学习者，大家可以跟我一起讨论各种问题喔。
🍎个人主页：Hhzzy99
🍊个人信条：坚持就是胜利！
💞当前专栏：Java数据结构与算法
🥭本文内容：Java实现单向链表的两种形式

单向链表

---

---

单向链表的特点

单向链表，顾名思义它是单向的，一个节点有数据部分和next指针部分组成，数据部分用来保存数据，next指针指向下一个节点，所以单向链表的每个节点都只知道下一个节点是什么，而不知道上一个节点是什么。

单向链表代码实现（无哨兵）

/****@description:单向链表*@author: Hhzzy99*@date:2023/3/4**/
public class SinglyLinkedList implements Iterable<Integer>{//整体private Node head = null;//头指针@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = head;@Overridepublic boolean hasNext() {//是否有下一个元素return p != null;}@Overridepublic Integer next() {//返回当前值，并指向下一个元素int value = p.value;p = p.next;return value;}};}/*** 节点类*/private static class Node{int value;//值Node next;//下一个结点指针public Node(int value, Node next) {this.value = value;this.next = next;}}/*** 链表头添加元素* @param value 元素值*/public void addFirst(int value){//1.链表为空
//        head = new Node(value,null);//2.链表非空head = new Node(value,head);}//链表遍历public void loop1(Consumer<Integer> consumer){Node p = head;while(p != null){consumer.accept(p.value);p = p.next;}}/*** for循环＋函数式接口Consumer* @param consumer 函数式接口*/public void loop2(Consumer<Integer> consumer){for (Node p = head; p != null; p = p.next){consumer.accept(p.value);}}/*** 最后一个元素* @return Node p*/private Node findLast(){if(head == null)return null;Node p;for(p = head; p.next != null; p = p.next){}return p;}/*** 最后面添加元素* @param value 元素值*/public void addLast(int value){Node last = findLast();if(last == null){addFirst(value);return;}last.next = new Node(value,null);}/*** 寻找索引为index的元素* @param index 寻找的元素的索引* @return Node p*/private Node findNode(int index){int i = 0;for(Node p = head; p.next != null; p = p.next,i++){if(i == index)return p;}return null;}/*** 获取索引位置的元素* @param index 索引值* @throws IllegalArgumentException - 找不到索引，抛出index非法异常*/public int get(int index){Node p = findNode(index);if(p == null)//抛异常throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));return p.value;}/*** 向索引位置插入元素* @param index 索引值* @param value 待插入值* @throws IllegalArgumentException - 找不到索引，抛出index非法异常*/public void insert(int index, int value){if(index == 0){addFirst(value);return;}Node prev = findNode(index - 1);//找到上一个节点if (prev == null)//找不到throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));prev.next = new Node(value,prev.next);}/*** 删除第一个元素* @throws IllegalArgumentException - 找不到索引，抛出index非法异常*/public void removeFirst(){if(head == null)throw new IllegalArgumentException(String.format("index [%d] 不合法%n",0));head = head.next;}/*** 删除索引为index的元素* @param index 要删除元素的索引值* @throws IllegalArgumentException - 找不到索引，抛出index非法异常*/public void remove(int index){if(index == 0){removeFirst();return;}Node prev = findNode(index - 1);//上一个节点if (prev == null)throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));if (prev.next == null)throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));prev.next = prev.next.next;//prev.next是被删除的元素}
}

测试T1

/****@description:测试*@author: Hhzzy99*@date:2023/3/4**/
public class TestSinglyLinkedList {private SinglyLinkedList getSinglyLinkedList() {//addFirst    addLastSinglyLinkedList singlyLinkedList = new SinglyLinkedList();singlyLinkedList.addFirst(1);singlyLinkedList.addLast(2);singlyLinkedList.addLast(3);singlyLinkedList.addLast(4);return singlyLinkedList;}@Test//测试get()public void test01(){SinglyLinkedList singlyLinkedList = getSinglyLinkedList();System.out.println(singlyLinkedList.get(2));System.out.println(singlyLinkedList.get(5));}@Test//测试insertpublic void test02(){SinglyLinkedList singlyLinkedList = getSinglyLinkedList();singlyLinkedList.loop1(value -> {System.out.print(value + ",");});System.out.println();System.out.println("=============");singlyLinkedList.insert(0,18);singlyLinkedList.loop1(value -> {System.out.print(value + ",");});}@Test//测试removepublic void test03(){SinglyLinkedList singlyLinkedList = getSinglyLinkedList();singlyLinkedList.loop1(value -> {System.out.print(value + ",");});System.out.println();singlyLinkedList.removeFirst();for (Integer ele:singlyLinkedList) {System.out.print(ele + ",");}System.out.println();}@Test//测似removepublic void test04(){SinglyLinkedList singlyLinkedList = getSinglyLinkedList();singlyLinkedList.loop1(value -> {System.out.print(value + ",");});System.out.println();singlyLinkedList.remove(2);for (Integer ele:singlyLinkedList) {System.out.print(ele + ",");}System.out.println();}
}

test01:第一个获取到值，第二个超出索引，抛出预设的异常

test02:符合预期

test03:符合预期

test04:符合预期

单向链表代码实现（有哨兵）

/****@description:单向链表（带哨兵）*@author: Hhzzy99*@date:2023/3/4**/
public class SinglyLinkedListSentinel implements Iterable<Integer>{//整体private Node head = new Node(999,null);//头指针->哨兵@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = head.next;@Overridepublic boolean hasNext() {//是否有下一个元素return p != null;}@Overridepublic Integer next() {//返回当前值，并指向下一个元素int value = p.value;p = p.next;return value;}};}/*** 节点类*/private static class Node{int value;//值Node next;//下一个结点指针public Node(int value, Node next) {this.value = value;this.next = next;}}/*** 链表头添加元素* @param value 元素值*/public void addFirst(int value){insert(0,value);}//链表遍历public void loop1(Consumer<Integer> consumer){Node p = head.next;while(p != null){consumer.accept(p.value);p = p.next;}}/*** for循环＋函数式接口Consumer* @param consumer 函数式接口*/public void loop2(Consumer<Integer> consumer){for (Node p = head.next; p != null; p = p.next){consumer.accept(p.value);}}/*** 最后一个元素* @return Node p*/private Node findLast(){Node p;for(p = head; p.next != null; p = p.next){}return p;}/*** 最后面添加元素* @param value 元素值*/public void addLast(int value){Node last = findLast();last.next = new Node(value,null);}/*** 寻找索引为index的元素* @param index 寻找的元素的索引* @return Node p*/private Node findNode(int index){int i = -1;//从哨兵位置开始(-1)for(Node p = head; p.next != null; p = p.next,i++){if(i == index)return p;}return null;}/*** 获取索引位置的元素* @param index 索引值* @throws IllegalArgumentException - 找不到索引，抛出index非法异常*/public int get(int index){Node p = findNode(index);if(p == null)//抛异常throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));return p.value;}/*** 向索引位置插入元素* @param index 索引值* @param value 待插入值* @throws IllegalArgumentException - 找不到索引，抛出index非法异常*/public void insert(int index, int value){if(index == 0){addFirst(value);return;}Node prev = findNode(index - 1);//找到上一个节点if (prev == null)//找不到throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));prev.next = new Node(value,prev.next);}/*** 删除第一个元素* @throws IllegalArgumentException - 找不到索引，抛出index非法异常*/public void removeFirst(){remove(0);}/*** 删除索引为index的元素* @param index 要删除元素的索引值* @throws IllegalArgumentException - 找不到索引，抛出index非法异常*/public void remove(int index){Node prev = findNode(index - 1);//上一个节点if (prev == null)throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));if (prev.next == null)throw new IllegalArgumentException(String.format("index [%d] 不合法%n",index));prev.next = prev.next.next;//prev.next是被删除的元素}
}

测试T2

private SinglyLinkedListSentinel getSinglyLinkedListSentinel() {SinglyLinkedListSentinel list = new SinglyLinkedListSentinel();list.addLast(1);list.addLast(2);list.addLast(3);list.addLast(4);return list;}@Testpublic void test05(){SinglyLinkedListSentinel list = getSinglyLinkedListSentinel();list.loop2(ele->{System.out.print(ele+",");});System.out.println();System.out.println(list.get(2));System.out.println(list.get(10));//抛异常}@Testpublic void test06(){SinglyLinkedListSentinel list = getSinglyLinkedListSentinel();list.loop2(ele->{System.out.print(ele+",");});System.out.println();list.insert(2,7);list.loop2(ele->{System.out.print(ele+",");});System.out.println();list.remove(1);list.loop2(ele->{System.out.print(ele+",");});
//        list.insert(7,19);//抛异常}

test05:符合预期，抛出预设异常

test06:符合预期

---

结语

本文展示了Java实现单向链表的代码，希望对大家有所帮助！大家如果感兴趣可以点点赞，关注一下，你们的支持是我最强大的动力，非常感谢您的阅读(❁´◡`❁)