单链表

介绍

单链表（Singly Linked List）是一种常见的数据结构，用于存储和组织数据。它由一系列节点组成，每个节点包含两个部分：数据部分和指向下一个节点的引用（指针）。

单链表的特点是每个节点只有一个指针，即指向下一个节点，而最后一个节点指向空（null），表示链表的结束。

下面是一个单链表的示例：

头节点 -> 节点1 -> 节点2 -> 节点3 -> ... -> 尾节点 -> null

头节点是链表的起始点，尾节点是链表的结束点。每个节点包含一个数据域，用于存储具体的数据，以及一个指针域，指向下一个节点。

通过头节点，可以遍历整个链表。要访问链表中的特定节点，需要从头节点开始，依次沿着每个节点的指针找到目标节点。

单链表的插入和删除操作相对简单高效。插入一个新节点时，只需修改相邻节点的指针即可，而不需要移动其他节点。删除节点时，只需修改前一个节点的指针，将其指向待删除节点的下一个节点，然后释放待删除节点的内存空间。

然而，由于单链表的节点只包含一个指针，因此无法直接访问前一个节点，因此在删除和插入节点时需要特别注意。

单链表在某些情况下具有一些优势，例如插入和删除操作频繁，且对随机访问的需求较少的情况。但是，由于无法直接访问前一个节点，获取某个节点的前驱节点的操作比较麻烦，并且无法实现常数时间的随机访问。

另外，还有其他类型的链表，如双向链表（Doubly Linked List），它在每个节点中包含两个指针，分别指向前一个节点和后一个节点，从而提供了更多的灵活性和功能。

代码实现

public class SinglyLinkedList<T> {
    //用于存储数据
    public class Node {
        public T data;
        public Node nextNode;

    }

    public Node headNode;
    public int size;

    public SinglyLinkedList() {
        headNode = null;
        size = 0;
    }

    public boolean isEmpty() {
        if (headNode == null) return true;
        return false;
    }

    //在链表的头结点插入数据
    public void insertAtHead(T data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = headNode;
        headNode = newNode;
        size++;
    }

    //在链表的尾结点插入数据
    public void insertAtEnd(T data) {
        if (isEmpty()) {
            insertAtHead(data);
            return;
        }
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = null;

        Node last = headNode;
        while (last.nextNode != null) {
            last = last.nextNode;
        }
        last.nextNode = newNode;
        size++;
    }

    //在给定节点后插入数据
    public void insertAfter(T data, T previous) {
        Node newNode = new Node();
        newNode.data = data;
        Node currentNode = this.headNode;
        while (currentNode != null && currentNode.data != previous) {
            currentNode = currentNode.nextNode;
        }
        if (currentNode != null) {
            newNode.nextNode = currentNode.nextNode;
            currentNode.nextNode = newNode;
            size++;
        }
    }

    //打印链表
    public void printList() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
            return;
        }
        Node temp = headNode;
        System.out.print("List : ");
        while (temp.nextNode != null) {
            System.out.print(temp.data.toString() + " -> ");
            temp = temp.nextNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }

    //在链表中查找给定值
    public boolean searchNode(T data) {
        Node currentNode = this.headNode;
        while (currentNode != null) {
            if (currentNode.data.equals(data))
                return true;
            currentNode = currentNode.nextNode;
        }
        return false;
    }

    //删除头结点数据
    public void deleteAtHead() {
        if (isEmpty())
            return;
        headNode = headNode.nextNode;
        size--;
    }

    //从linked list中删除指定的值
    public void deleteByValue(T data) {
        if (isEmpty())
            return;

        //从头结点开始
        Node currentNode = this.headNode;
        Node prevNode = null; 

        if(currentNode.data.equals(data)) {
            //删除头部节点
            deleteAtHead();
            return;
        }
        //遍历链表来删除指定的值
        while (currentNode != null) {
            //找了待删除数据
            if (data.equals(currentNode.data)){
                prevNode.nextNode = currentNode.nextNode;
                size--;
                return; 
            }
            prevNode = currentNode;
            currentNode = currentNode.nextNode;
        }
    }
}

单链表

# 单链表

# 介绍

# 代码实现

单链表

介绍

代码实现