算法与数据结构-单链表（Singly Linked List）

了解数据结构的小伙伴，应该有听说过单链表。那么是单链表呢？单链表的使用是怎么样的呢？下面就分享一下我理解的单链表。

单链表概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表示例图

在这里插入图片描述

单链表操作Demo

1.创建一个单链表类Node

package com.wyb.list;

// 一个节点
public class Node {
    // 节点内容
    int data;
    
    // 下一个节点
    Node next;
    
    public Node(int data) {
        this.data = data;
    }
    
    // 为节点追加节点
    public Node append(Node node) {
        // 当前节点
        Node currentNode = this;
        // 循环向后找
        while(true) {
            // 取出下一个界面
            Node nextNode = currentNode.next;
            // 如果下一个节点为null,当前界面已经是最后一个节点
            if(nextNode == null) {
                break;
            }
            // 赋值给当前节点 
            currentNode = nextNode;
        }
        // 把需要追加的节点追加为找到的当前节点的下一个节点
        currentNode.next = node;
        return this;
    }
    
    // 删除下一个节点
    public void removeNext() {
        // 取出下下一个节点
        Node newNext = next.next;
        // 把下下一个节点设置为当前节点的下一个节点
        this.next = newNext;
    }
    
    // 插入一个节点
    public void after(Node node) {
        // 取出一个节点，作为下下一个节点
        Node nextNext = next;
        // 把新节点作为当前节点的下一个节点
        this.next = node;
        // 把下下一个节点设置为新节点的下一个节点
        node.next = nextNext;   
    }
    
    // 显示所有节点信息
    public void show() {
        Node currentNode = this;
        while(true) {
            System.out.print(currentNode.data+" ");
            // 取出下一个节点
            currentNode = currentNode.next;
            // 如果是最后一个节点
            if(currentNode ==null) {
                break;
            }
        }
    }
    
    // 获取下一个节点的方法
    public Node next() {
        return this.next;
    }
    
    // 获取节点中的数据
    public int getDate() {
        return this.data;
    }
    
    // 当前节点是否是最后一个节点
    public boolean isLast() {
        return next == null;
    }
}

2.创建一个测试类TestNode

package com.wyb.list;

public class TestNode {

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        // 追加节点
        n1.append(n2).append(n3).append(new Node(4));
        // 取出下一个节点
//      System.out.println(n1.next().next().next().getDate());
        // 判断节点是否为最后一个节点x
//      System.out.println(n1.isLast());
//      System.out.println(n1.next().next().next().isLast());
        // 显示所有节点信息
        n1.show();
        // 删除一个节点
//      n1.next().removeNext();
        // 显示所有节点信息
//      n1.show();
        System.out.println();
        // 插入一个新节点
        Node node = new Node(5);
        n1.next().after(node);
        n1.show();
    }
}

关于单链表的知识大概是这些，希望对看文章小伙伴们有所帮助。