前面我们介绍了栈与队列的 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();
}
}
}
