Java数据结构之链表(动力节点之Java学院整理)

什么是链表

链表是一种数据结构，它是由一系列节点组成的，每个节点包含数据和一个指向下一个节点的指针。与数组不同，链表中的节点在内存中不是连续存储的，而是通过指针来连接。链表的基本形式包括单向链表、双向链表和循环链表。

链表的优缺点

优点

• 可以充分利用计算机的空间，实现灵活的内存动态管理。
• 插入和删除操作时间复杂度为O(1)，相对数组快很多。

缺点

• 随机访问性能较差，需要从头开始遍历。
• 占用额外的空间存储指针信息。

链表的实现

链表的实现一般包括节点定义和相应的链表操作。下面是一个简单的单向链表的实现。

节点定义

public class Node{
    public int val;
    public Node next;

    public Node(int val){
        this.val = val;
    }   
}

添加节点

public Node addNode(Node head, int val){
    Node newNode = new Node(val);
    if(head == null){
        return newNode;
    }
    Node p = head;
    while(p.next != null){
        p = p.next;
    }
    p.next = newNode;
    return head;
}

删除节点

public Node deleteNode(Node head, int val){
    if(head == null){
        return null;
    }
    if(head.val == val){
        return head.next;
    }
    Node pre = head;
    Node cur = head.next;
    while(cur != null){
        if(cur.val == val){
            pre.next = cur.next;
            return head;
        }
        pre = cur;
        cur = cur.next;
    }
    return head;
}

示例

下面是一个简单的示例，展示了如何创建一个链表并添加、删除节点。

public static void main(String[] args) {
    Node head = null;
    int[] arr = {1,2,3,4,5};
    for(int i = 0; i < arr.length; i++){
        head = addNode(head, arr[i]);
    }
    printList(head);
    head = deleteNode(head, 3);
    printList(head);
}

public static void printList(Node head){
    Node p = head;
    while(p != null){
        System.out.print(p.val + " ");
        p = p.next;
    }
    System.out.println();
}

输出结果：

1 2 3 4 5 
1 2 4 5 

以上就是链表的基本实现，可以根据需要进行相应扩展，例如双向链表、循环链表等。