首页 > 代码库 > 算法(第4版)-1.3.3 链表

算法(第4版)-1.3.3 链表

总结:本小节讲述了链表的概念,以及用链表实现Stack、Queue和Bag的过程和优缺点。

 

重点:

1. 定义:链表是一种递归的数据结构,它或者为空(null),或者是指向一个结点(node)的引用,该结点含有一个泛性的元素和一个指向另一条链表的引用。

 

2. 我们首先用一个嵌套类来定义结点的抽象数据类型:

private class Node {
    Item item;
    Node next;
}

它们实现的不是抽象数据类型,因为我们会直接使用其实例变量。

 

3. 所需的时间和链表的长度无关的三种操作:

· 在表头插入结点;

· 从表头删除结点;

· 在表尾插入结点。

这是重点,一定要理解!

 

4. 实现任意插入和删除操作的标准解决方案是使用双向链表,其中每个结点都含有两个链接,分别指向不同的方向。

 

5. 栈的实现(原因:3):

当使用push()压入一个元素时,我们会按照1.3.3.3节所讨论的代码将该元素添加在表头;

当使用pop()删除一个元素时,我们会按照1.3.3.4节讨论的代码将该元素从表头删除。

public class Stack<Item> {
    private Node first;    // 栈顶(最近添加的元素)
    private int N;            // 元素数量
    private class Node {
        // 定义了结点的嵌套类
        Item item;
        Node next;
    }
    public boolean isEmpty() {
        return first == null;
    }
    public int size() {
        return N;
    }
    public void push(Item item) {
        // 向栈顶添加元素
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    public Item pop() {
        // 从栈顶删除元素
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
}

链表的方向:栈顶 -> 栈底

 

6. 队列的实现(原因:3):

要将一个元素入列(enqueue()),我们就将它添加到表尾(在链表为空时需要将first和last都指向新结点);

要将一个元素出列(dequeue()),我们就删除表头的结点(当链表为空时需要更新last的值)。

public class Queue<Item> {
    private Node first;    // 指向最早添加的结点的链接
    private Node last;    // 指向最近添加的结点的链接
    private int N;            // 队列中的元素数量
    private class Node {
        // 定义了结点的嵌套类
        Item item;
        Node next;
    }
    public boolean isEmpty() {
        return first == null;    // 或: N == 0.
    }
    public int size() {
        return N;
    }
    public void enqueue(Item item) {
        // 向表尾添加元素
        Node oldlast = last;
        last = new Node();
        last.item = item;
        last.next = null;
        if (isEmpty())    first = last;
        else                        oldlast.next = last;
        N++;
    }
    public Item dequeue() {
        // 从表头删除元素
        Item item = first.item;
        first = first.next;
        if (isEmpty())    last = null;
        N--;
        return item;
    }
}

链表的方向:队头 -> 队尾

 

7. 链表的使用达到了我们的最优设计目标:

· 它可以处理任意类型的数据;

· 所需的空间总是和集合的大小成正比;

· 操作所需的时间总是和集合的大小无关。

 

8. 编程语言历史上的一块里程碑就是McCathy在20世纪50年代发明的LISP语言,而链表则是这种语言组织程序和数据的主要结构。

 

9. 背包的实现:

只需要将Stack中的push()改名为add(),并去掉pop()的实现即可。

import java.util.Iterator;

public class Bag<Item> implements Iterable<Item> {
    private Node first;    // 链表的首结点
    private int N;
    private class Node {
        Item item;
        Node next;
    }
    public boolean isEmpty() {
        return first == null;
    }
    public int size() {
        return N;
    }
    public void add(Item item) {
        // 和Stack的push()方法完全相同
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    public Iterator<Item> iterator() {
        return new ListIterator();
    }
    private class ListIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext() {
            return current != null;
        }
        public void remove() {}
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

*hasNext()方法会检测current是否为null。

算法(第4版)-1.3.3 链表