概述

• 链表是一种通过指针串联在一起的线性结构

• 链表在内存中的存储形式
  • 链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上
• 链表有节点组成，每个节点又分成两个部分：1）数据域 (data) 2）指针域
  • 数据域：存放数据
  • 指针域：存放指针，指向节点
• 头节点(head)
  • 链表需要创建一个头节点来指定头，该节点数据域为null，指针初始化为null
  • 当第一个节点加入时，将头节点的指针指向第一个节点
  • 头节点只具有指向作用
• 链表又分为
  • 单链表
  • 双链表
  • 循环链表

单链表

• 只有一个指针域，指向下一个节点 ，称为next

• 最后一个节点的指针指向null

/**
 * @author 发着呆看星
 * @create 2023/3/29
 **/
public class Node<E> {
    // 节点id
    private int no;
    // 数据域
    private E data;
    // 指针域，指向下一个节点
    public Node<E> next;

    public Node(int no, E data) {
        this.no = no;
        this.data = data;
    }

    public Node() {
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public E getData() {
        return data;
    }

    public void setData(E data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", data=" + data +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node<?> node = (Node<?>) o;
        return no == node.no;
    }

    @Override
    public int hashCode() {
        return Objects.hash(no);
    }
}

/**
 * @author 发着呆看星
 * @create 2023/3/29
 **/
public class SingleLinkedList<E> {
    // 创建头节点 ，只具有指向功能
    /*
	 也可以没有 ，加入的第一个节点即为头节点
      private Node<E> head = null;   加入第一个时判断 ，head = 第一个节点
	*/
   
    private Node<E> head = new Node<>();

    // 去重添加节点操作，添加至链表末尾
    public void addNode(Node<E> node) {
        Node<E> temp;
        if (head.next == null) {
            head.next = node;
            return;
        }
        if (head.next.equals(node)) {
            System.out.println("链表中已存在该元素");
            return;
        } else {
            temp = head.next;
        }
        while (true) {
            if (temp.equals(node)){
                System.out.println("链表中已存在该元素");
                return;
            }
            if (temp.next == null) {
                temp.next = node;
                break;
            }
            temp = temp.next;
        }
    }

    // 遍历链表
    public void showLinkedList() {
        if (head.next == null) {
            System.out.println("当前链表为空");
            return;
        }
        Node<E> temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    // 删除指定节点
    // 单链表删除节点应该找到要删除节点的前一个节点
    public void delete(int no){
        if (head.next == null){
            System.out.println("当前链表没有元素，不能进行删除操作");
            return;
        }
        Node<E> temp =  head;
        while (temp.next != null){
            if (temp.next.getNo() == no) {
                temp.next = temp.next.next;
                return;
            }
            temp = temp.next;
        }
        System.out.println("链表中没有你想要删除的元素");
    }

    // 修改节点
    public void update(Node<E> node){
        if (head.next == null){
            System.out.println("当前链表没有元素，不能进行修改操作");
            return;
        }
        Node<E> temp = head.next;
        while (temp != null){
            if (temp.getNo() == node.getNo()){
                temp.setData(node.getData());
                return;
            }
            temp = temp.next;
        }
        System.out.println("当前链表没有你想要修改的节点");
    }
}

public static void main(String[] args) {
    SingleLinkedList<String> sll = new SingleLinkedList<>();
    boolean loop = true;
    Scanner scanner = new Scanner(System.in);
    int no;
    while (loop){
        System.out.println("==================================");
        System.out.println("(a)：添加节点");
        System.out.println("(u)：修改节点");
        System.out.println("(r)：删除指定节点");
        System.out.println("(l)：查看链表");
        System.out.println("(e)：退出程序");
        System.out.print("请选择你要的操作：");
        char c = scanner.next().charAt(0);
        switch (c){
            case 'a':
            case 'u':
                System.out.print("请输入节点的编号：");
                no = scanner.nextInt();
                System.out.print("请输入节点的数据：");
                String data = scanner.next();
                Node<String> stringNode = new Node<>(no,data);
                sll.addNode(stringNode);
                break;
            case 'r':
                System.out.print("请输入想要删除节点的编号：");
                no = scanner.nextInt();
                sll.delete(no);
                break;
            case 'l':
                sll.showLinkedList();
                break;
            case 'e':
                loop = false;
                break;
        }
        System.out.println();
    }
}

双链表

• 双链表有两个指针域，一个指向上一个节点 ，一个指向下一个节点
• 第一个节点指向上一个节点的指针域为null
• 最后一个节指向下一个节点的指针域为null

循环链表

• 循环链表：即首位相连的链表

• 和普通链表不同的是，循环链表的最后一个节点的 next 指向 第一个节点