本文主要是介绍Java-单向链表实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
什么是链表?
链表是一种常见的数据结构,用于存储一系列元素。与数组不同,链表中的元素(节点)在内存中不必是连续的。每个节点包含数据部分和指向下一个节点的引用(指针)。链表的主要优点是插入和删除操作的时间复杂度为O(1),但访问特定元素的时间复杂度为O(n)。
头节点
在单链表的数据结构中,头节点并不是一个独立的节点,而是一个指针或引用,指向链表中第一个数据节点。它的作用是标记链表的起始位置,以便能够遍历和操作链表中的所有节点。在大多数的单链表实现中,“头节点”本身并没有特别之处,它仅仅是一个指向第一个有效节点的引用。
什么是哨兵节点?
哨兵节点(也称为哑节点或伪节点)是一个特殊的节点,通常不包含实际数据,仅用于简化链表的操作。在单向链表中,哨兵节点通常作为头节点使用,使得链表的插入、删除等操作更加统一和简单。
代码实现:
没有将头节点设置为哨兵节点,以下是单向链表的Java实现代码,并解释了关键部分:
package school.singlelinkedlist;import java.util.Iterator;
import java.util.function.Consumer;/*** 文件名: null.java* 作者: 20526* 创建时间: 2024/9/6 15:17* 描述:单向链表实现*/
public class SingleLinkedList implements Iterable<Integer>{private Node head = null; // 头节点//节点类public static class Node {int data;Node next;public Node(int data, Node next) {this.data = data;this.next = next;}}//链表遍历public void traverse(Consumer <Integer> consumer) {Node current = head;//定义一个指针,进行遍历,默认指向头节点while (current!= null) {consumer.accept(current.data);//调用consumer.accept(data)方法,对当前节点的数据进行处理current = current.next;//指针向后移动}}public void traverse2(Consumer <Integer> consumer){for (Node current = head; current!= null; current = current.next){consumer.accept(current.data);}}//实现迭代器,可以用增强for循环遍历@Overridepublic Iterator<Integer> iterator() {//匿名内部类return new Iterator<Integer>() {Node current = head;@Overridepublic boolean hasNext() { //判断是否有下一个节点return current!= null;}@Overridepublic Integer next() { //返回当前值,并指向下一个节点int value = current.data;current = current.next;return value;}};}//添加节点到链表头public void addfirst(int data) {
// head = new Node(data, null);head = new Node(data, head);}//查找链表尾节点private Node findlast(){Node p ;if (head == null)return null;for (p = head; p.next!= null; p = p.next){}return p;}//添加节点到链表尾public void addlast(int data){Node last = findlast();if (last == null) {addfirst(data);return;}else{last.next = new Node(data, null);}}//根据索引插入节点public void add(int index, int data) throws IllegalArgumentException {if (index == 0 ) {addfirst(data);return;}Node prev = findNode(index-1);if (prev == null) {throw illegalIndex(index);}prev.next = new Node(data, prev.next);}//查找节点private Node findNode(int index) {int i = 0;for (Node p = head; p!= null; p = p.next,i++){if (i == index)return p;}return null;//如果没有找到,返回null}public int get(int index) {Node p = findNode(index);if (p == null){illegalIndex(index);}return p.data;}//索引不合法,抛出异常private IllegalArgumentException illegalIndex(int index) {throw new IllegalArgumentException(String.format("Index: [%d]不合法%n", index));}//删除首节点public void removefirst(int index) {if (head == null)throw new IllegalArgumentException("空链表");head = head.next;}//根据索引删除节点public void remove(int index) {if (index == 0) {removefirst(index);return;}Node prev = findNode(index-1);//上一个节点if (prev == null) {throw illegalIndex(index);}Node remove = prev.next;//被删除的节点if (remove == null) {throw illegalIndex(index);}prev.next = remove.next;}// 根据索引修改节点的值public void set(int index, int data) throws IllegalArgumentException {Node node = findNode(index); // 查找指定索引的节点if (node == null) {throw illegalIndex(index); // 如果节点不存在,抛出索引不合法的异常}node.data = data; // 修改节点的值}}
测试代码:
package school.singlelinkedlist;import org.junit.Test;public class SingleLinkedListTest {@Testpublic void test1() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addfirst(2);list.addfirst(3);list.addfirst(4);list.addfirst(5);list.traverse(data -> {System.out.println(data + " ");});list.traverse2(data -> {System.out.println(data + " ");});}@Testpublic void test2() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addfirst(2);list.addfirst(3);list.addfirst(4);list.addfirst(5);for (Integer i : list) {System.out.println(i);}}@Testpublic void test3() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addlast(2);list.addlast(3);list.addlast(4);for (Integer i : list) {System.out.println(i);}}@Testpublic void test4() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addlast(2);list.addlast(3);list.addlast(4);System.out.println(list.get(0));System.out.println(list.get(1));}@Testpublic void test5() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addlast(2);list.addlast(3);list.addlast(4);list.add(2, 5);
// list.add(6, 6);for (Integer i : list) {System.out.println(i);}}@Testpublic void test6() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addlast(2);list.addlast(3);list.addlast(4);list.addlast(5);for (Integer i : list) {System.out.println(i);}System.out.println("------------删除后-------------");
// list.removefirst(0);list.remove(2);for (Integer i : list) {System.out.println(i);}}@Testpublic void test7() {SingleLinkedList list = new SingleLinkedList();list.addfirst(1);list.addlast(2);list.addlast(3);list.addlast(4);list.addlast(5);list.set(1,1);for (Integer i : list) {System.out.println(i);}}}
关键点解释
head = new Node(data, head);
这行代码的作用是在链表的头部添加一个新节点。具体解释如下:
new Node(data, head)
:
new Node(data, head)
是通过调用Node
类的构造函数来创建一个新的节点对象。在构造函数中,data
代表新节点的数据值,而head
代表当前头节点,即链表的第一个节点。- 通过传入
head
作为构造函数的第二个参数,新节点的next
指针将指向当前的头节点。因此,新节点成为链表中的第一个节点,而原来的头节点成为新节点的下一个节点。
head = new Node(data, head);
:
- 这行代码将
head
引用更新为新的节点对象。通过这种方式,链表的头节点即被更新为新创建的节点。
简而言之,这个操作在链表的头部插入了一个新的节点,使新的节点成为链表的第一个节点。旧的头节点则被移到第二个位置。
头节点设置为哨兵节点
package school.singlelinkedlist;import java.util.Iterator;
import java.util.function.Consumer;/*** 文件名: null.java* 作者: 20526* 创建时间: 2024/9/6 15:17* 描述:单向链表实现*/
public class SingleLinkedList implements Iterable<Integer>{// private Node head = null; // 头节点private Node head = new Node(0, null);//节点类public static class Node {int data;Node next;public Node(int data, Node next) {this.data = data;this.next = next;}}//链表遍历public void traverse(Consumer <Integer> consumer) {Node current = head.next;//定义一个指针,进行遍历,默认指向头节点while (current!= null) {consumer.accept(current.data);//调用consumer.accept(data)方法,对当前节点的数据进行处理current = current.next;//指针向后移动}}public void traverse2(Consumer <Integer> consumer){for (Node current = head.next; current!= null; current = current.next){consumer.accept(current.data);}}//实现迭代器,可以用增强for循环遍历@Overridepublic Iterator<Integer> iterator() {//匿名内部类return new Iterator<Integer>() {Node current = head.next;@Overridepublic boolean hasNext() { //判断是否有下一个节点return current!= null;}@Overridepublic Integer next() { //返回当前值,并指向下一个节点int value = current.data;current = current.next;return value;}};}//添加节点到链表头public void addfirst(int data) {add(0, data);}//查找链表尾节点private Node findlast(){Node p ;for (p = head; p.next!= null; p = p.next){}return p;}//添加节点到链表尾public void addlast(int data){Node last = findlast();last.next = new Node(data, null);}//根据索引插入节点public void add(int index, int data) throws IllegalArgumentException {Node prev = findNode(index-1);if (prev == null) {throw illegalIndex(index);}prev.next = new Node(data, prev.next);}//查找节点private Node findNode(int index) {int i = -1;for (Node p = head; p!= null; p = p.next,i++){if (i == index)return p;}return null;//如果没有找到,返回null}public int get(int index) {Node p = findNode(index);if (p == null){illegalIndex(index);}return p.data;}//索引不合法,抛出异常private IllegalArgumentException illegalIndex(int index) {throw new IllegalArgumentException(String.format("Index: [%d]不合法%n", index));}//删除首节点public void removefirst(int index) {remove(0);}//根据索引删除节点public void remove(int index) {Node prev = findNode(index-1);//上一个节点if (prev == null) {throw illegalIndex(index);}Node remove = prev.next;//被删除的节点if (remove == null) {throw illegalIndex(index);}prev.next = remove.next;}// 根据索引修改节点的值public void set(int index, int data) throws IllegalArgumentException {Node node = findNode(index); // 查找指定索引的节点if (node == null) {throw illegalIndex(index); // 如果节点不存在,抛出索引不合法的异常}node.data = data; // 修改节点的值}}
下面是将头节点设置为哨兵节点后的改动优化,与上面的略有不同,不过大致思路都一样,去掉了一些特殊情况的处理
哨兵节点:代码中
private Node head = new Node(0, null);
定义了一个哨兵节点。这个节点不存储实际数据,仅用于简化链表操作。遍历方法:
traverse
和traverse2
方法展示了两种遍历链表的方式,均使用Consumer
接口来处理每个节点的数据。迭代器实现:
iterator
方法实现了Iterable
接口,使得链表可以通过增强for循环进行遍历。插入和删除操作:
add
和remove
方法展示了如何在链表中插入和删除节点。由于使用了哨兵节点,这些操作变得更加简单和统一。异常处理:
illegalIndex
方法用于处理索引不合法的情况,抛出IllegalArgumentException
异常。
通过使用哨兵节点,链表的操作变得更加简洁和高效,避免了在处理头节点时需要特殊处理的麻烦。 希望对你有所帮助……
这篇关于Java-单向链表实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!