数据结构(三) -- 单链表

前面我们介绍了栈与队列的 ADT，并利用数组加以实现。遗憾的是，尽管这种实现简单明了，但由于数组长度必须固定，在空间效率及适应性方面还存在不足。本文将介绍一种基于链表的实现，以消除上述缺陷。

一，单链表

所谓链表（Linked list），就是按线性次序排列的一组数据节点，每个节点都是一个对象，它通过一个引用element指向对应的数据元素，同时还通过一个引用next指向下一节点。

每个节点的next 引用都相当于一个链接或指针，指向另一节点。借助于这些next 引用，我们可以从一个节点移动至其它节点。链表的第一个和最后一个节点，分别称作链表的首节点（Head）和末节点（Tail）。末节点的特征是，其next 引用为空。如此定义的链表，称作单链表（Singly linkedlist）。

---

二，节点的代码实现

• 抽象出位置（Position）这一概念，使我们既能够保持链表结构高效性，而又不致违背面向对象的设计原则。
  Position ADT的接口:

/*
* 位置ADT接口
*/
package dsa;
public interface Position {
    public Object getElem();//返回存放于该位置的元素
    public Object setElem(Object e);//将给定元素存放至该位置，返回此前存放的元素
}

节点：

public class Node implements Position {
    private Object element;// 数据对象
    private Node next;// 指向后继节点

    /**************************** 构造函数 ****************************/
    public Node() {
        this(null, null);
    }// 指向数据对象、后继节点的引用都置空

    public Node(Object e, Node n) {
        element = e;
        next = n;
    }// 指定数据对象及后继节点

    /**************************** Position接口方法 ****************************/
    // 返回存放于该位置的元素
    public Object getElem() {
        return element;
    }

    // 将给定元素存放至该位置，返回此前存放的元素
    public Object setElem(Object e) {
        Object oldElem = element;
        element = e;
        return oldElem;
    }

    /**************************** 单链表节点方法 ****************************/
    // 取当前节点的后继节点
    public Node getNext() {
        return next;
    }

    // 修改当前节点的后继节点
    public void setNext(Node newNext) {
        next = newNext;
    }

}

---

三，基于单链表实现栈

package dsa.Stack;

import other.Node;

public class Stack_List implements Stack {
    protected Node top;// 指向栈顶元素
    protected int size;// 栈中元素的数目

    // 构造方法（空栈）
    public Stack_List() {
        top = null;
        size = 0;
    }

    // 查询当前栈的规模
    public int getSize() {
        return size;
    }

    // 判断是否栈空
    public boolean isEmpty() {
        return (top == null) ? true : false;
    }

    // 压栈
    public void push(Object elem) {
        Node v = new Node(elem, top);// 创建一个新节点，将其作为首节点插入
        top = v;// 更新首节点引用
        size++;// 更新规模记录
    }

    // 读取（但不删除）栈顶
    public Object top() throws ExceptionStackEmpty {
        if (isEmpty())
            throw new ExceptionStackEmpty("意外：栈空");
        return top.getElem();
    }

    // 弹出栈顶
    public Object pop() throws ExceptionStackEmpty {
        if (isEmpty())
            throw new ExceptionStackEmpty("意外：栈空");
        Object temp = top.getElem();
        top = top.getNext();// 更新首节点引用
        size--;// 更新规模记录
        return temp;
    }
}

---

四，基于单链表实现队列

package dsa.Queue;

import other.Node;

public class Queue_List implements Queue {
    protected Node head;// 指向表首元素
    protected Node tail;// 指向表末元素
    protected int size;// 队列中元素的数目

    // 构造方法（空队列）

    public Queue_List() {
        head = tail = null;
        size = 0;
    }

    // 查询当前队列的规模
    public int getSize() {
        return size;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return (0 == size) ? true : false;
    }

    // 入队
    public void enqueue(Object obj) {
        Node node = new Node();
        node.setElem(obj);
        node.setNext(null);// 新节点作为末节点插入
        if (0 == size)
            head = node;// 若此前队列为空，则直接插入
        else
            tail.setNext(node);// 否则，将新节点接至队列末端
        tail = node;// 更新指向末节点引用
        size++;// 更新规模
    }

    // 出队
    public Object dequeue() throws ExceptionQueueEmpty {
        if (0 == size)
            throw new ExceptionQueueEmpty("意外：队列空");
        Object obj = head.getElem();
        head = head.getNext();
        size--;
        if (0 == size)
            tail = null;// 若队列已空，须将末节点引用置空
        return obj;
    }

    // 取（并不删除）队首元素
    public Object front() throws ExceptionQueueEmpty {
        if (isEmpty())
            throw new ExceptionQueueEmpty("意外：队列空");
        return head.getElem();
    }

    // 遍历（不属于ADT）
    public void Traversal() {
        Node p = head;
        while (null != p) {
            System.out.print(p.getElem() + " ");
            p = p.getNext();
        }
    }
}