链表 Linked List

定义

类型

info

堆栈、队列、树和图都能够使用链表实现，或者基于链表实现。

基本操作

1. 插入数据: 将一个元素插入到链表的任意位置。
2. 删除: 将一个元素从链表删除。
3. 查找(遍历): 查找一个特定的元素。
4. 更新: 更新一个特定节点上的元素。

Java 实现

定义

public class LinkedList {
    static class ListNode {
        int val;
        ListNode next;
        public Listnode (int val) {
            this.val = val;
        }
    }
    ListNode head;
    ListNode tail;
    int size;
    public LinkedList() {
        head = null;
        tail = null;
        size = 0;
    }
}

操作

public void append(int number) {
    ListNode newNode = new ListNode(number);
    if (tail == null) { // 空链表
        tail = newNode
    } else {
        tail.next = newNode;
        tail = newNode;
    }
    size++;
}
public void insert(int position, int number) {
    if (position > size) {
        return ;
    }
    ListNode newNode = newListNode(number);
    if (position == 0) {
        newNode.next = head;
        head = newNode;
        if(tail == null) {
            tail = newNode;
        }
        size++;
    } else if (position == size) {
        this.append(number);
    } else {
        ListNode prev = head;
        for (int i=0; i < position-1; i++) {
            prev = prev.next;
        }
        ListNode next = prev.next;
        newNode.next = next;
        prev.next = newNode;
        size++;
    }
}
public void delete(int number) {
    if(head != null && head.val == number) {
        head = head.next;
        size--;
        if(size == 0) { // Cornor case: no element is left
            tail  = head;
        }
    } else {
        ListNode prev = head;
        Listnode cur = head;
        while (prev != null && cur != null) {
            if(cur.val == number) {
                if (cur == tail) { // Cornor case: delete the lastest elemnt
                    tail = prev;
                }
                prev.next = cur.next;
                size--;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }
}
public int search (int number) {
    ListNode cur = head;
    for (int index = 0; cur != null; index++) {
        if (cur.val == number) {
            return index;
        }
        cur = cur.next;
    }
    return -1;
}
public int update(int oldValue, int newVlaue) {
    ListNode cur = head;
    for (int index = 0; cur != null; index++) {
        if (cur.val == oldValue) {
            cur.val = newValue;
            return index
        }
        cur = cur.next;
    }
    return -1;
}

复杂度分析

• 插入: O(n)
• 删除: O(n)
• 查找: O(n)
• 更新: O(n)

单向链表的思想: 双指针

Java.util.LinkedList

方法

• offer(), offerFirst(), offerLast()
• peek(), peekFirst(), peekLast()
• poll(), pollFirst(), pollLast()
• listIterator()
  • hasNext()
  • next()

来源

链表 Linked List【数据结构和算法入门 4】: https://www.youtube.com/watch?v=Vw7f6NqHCJk&list=PLV5qT67glKSGFkKRDyuMfwcL-hwXOc4q_&index=4