Java数据结构与算法之单链表深入理解

Java数据结构与算法之单链表深入理解攻略

什么是单链表？

单链表（Singly Linked List）是指一个节点只指向下一个节点的链表。

单链表由多个节点组成，每个节点有两个属性：数据域和指针域。数据域保存节点的数据，指针域保存下一个节点的指针，因此每个节点包含两个域：data和next。

单链表的基本操作

单链表常用的基本操作包括：

1. 在链表头部添加元素
2. 在链表尾部添加元素
3. 在链表中间插入元素
4. 删除链表中的某个元素
5. 遍历链表

具体操作的实现代码如下：

在链表头部添加元素

public class LinkedList<T> {
    private Node<T> head;

    public void addFirst(T data) {
        head = new Node<>(data, head);
    }
}

在链表尾部添加元素

public class LinkedList<T> {
    private Node<T> head;

    public void addLast(T data) {
        if (head == null) {
            addFirst(data);
        } else {
            Node<T> ptr = head;
            while (ptr.next != null) {
                ptr = ptr.next;
            }
            ptr.next = new Node<>(data, null);
        }
    }

}

在链表中间插入元素

public class LinkedList<T> {
    private Node<T> head;

    public void addAfter(T item, T newItem) {
        if (head == null) {
            throw new NoSuchElementException();
        }
        Node<T> ptr = head;
        while (ptr != null && !ptr.data.equals(item)) {
            ptr = ptr.next;
        }
        if (ptr == null) {
            throw new NoSuchElementException();
        }
        ptr.next = new Node<>(newItem, ptr.next);
    }
}

删除链表中的某个元素

public class LinkedList<T> {
    private Node<T> head;

    public void remove(T item) {
        if (head == null) {
            throw new NoSuchElementException();
        }
        if (head.data.equals(item)) {
            head = head.next;
            return;
        }
        Node<T> ptr = head;
        while (ptr.next != null && !ptr.next.data.equals(item)) {
            ptr = ptr.next;
        }
        if (ptr.next == null) {
            throw new NoSuchElementException();
        }
        ptr.next = ptr.next.next;
    }

}

遍历链表

public class LinkedList<T> {
    private Node<T> head;

    public void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (Node<T> ptr = head; ptr != null; ptr = ptr.next) {
            action.accept(ptr.data);
        }
    }
}

单链表的应用

单链表可以应用到栈、队列的实现以及图的广度优先遍历等。

示例一：栈的实现

public class Stack<T> {
    private final LinkedList<T> list = new LinkedList<>();

    public void push(T data) {
        list.addFirst(data);
    }

    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T item = peek();
        list.remove(item);
        return item;
    }

    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return list.getFirst();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }
}

示例二：图的广度优先遍历

public class Graph {
    private final LinkedList<Integer>[] adj;

    public Graph(int size) {
        adj = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int v, int w) {
        adj[v].addLast(w);
    }

    public void BFS(int s) {
        boolean[] visited = new boolean[adj.length];
        LinkedList<Integer> queue = new LinkedList<>();
        visited[s] = true;
        queue.add(s);
        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");
            for (int i = 0; i < adj[s].size(); i++) {
                int n = adj[s].get(i);
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

总结

单链表是一种常用的数据结构，是栈、队列实现和图搜索算法中基础的数据结构之一。针对单链表的基本操作，我们除了掌握其操作的实现方法，更需要理解其操作的本质意义和实际意义，才能更好地应用到具体的场景中。