数据结构与算法学习笔记(11):图解数据结构与算法-链表（一）&（二）&（三）：单链表的概念与结构

立即学习:https://edu.csdn.net/course/play/29510/420452?utm_source=blogtoedu

链表（一）&（二）&（三）：单链表的概念与结构

 

链表的概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

 

链表类型

单链表  双向链表  循环链表

 

单链表

单链表的构造

【思路】

一个结点，一块存储数据，并有一个指针引向下一个结点

/*
* 如何构造一个单链表？
* 成员变量：
* 1.head头结点
* 2.data数据块
* 3.next结点指引
* */

public Class Node{
    private Node head;
    private Object data;
    private Node next;
    
    public Node(Object data){
        this.data = data;
    }
    public Node(){}
    
    public void add(Object data){
        Node node = new Node(data);
        if(head == null){
            head = node;
            return;
        }
        Node temp = head; 
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = node;
    }

    public static void main(String[] args) {
        Node node = new Node();
        node.add(1);
        System.out.println(node.head.data);
        node.add(2);
        System.out.println(node.head.next.data);
        node.add(3);
        System.out.println(node.head.next.next.data);
        node.add(4);
        System.out.println(node.head.next.next.next.data);
        node.add(5);
        System.out.println(node.head.next.next.next.next.data);
    }
}

单链表的优劣

单链表中，每个结点的数据域都是通过一个Object类的对象引用来指引数据元素的，与数组类似，单向链表中的结点也具有一个线性次序，即如果结点a1的next引用指向结点a2，则a1就是a2的直接前驱，a2是a1的直接后续。只能通过前驱节点找到后续节点，而无法从后续节点找到前驱节点。

顺序存储（比如数组）内存空间固定，根据角标查找就可以直接找到。链式存储，需要一个一个的查询下一节点位置。