1、链表
在Java中实现链表，每个节点都有一个值，然后把它链接到下一个节点。下面来看一下节点的实现
class Node<E> {
private E e;
private Node<E> next = null;
Node() {
}
Node(E e) {
this.e = e;
}
public void setNext(Node<E> next) {
this.next = next;
}
public Node<E> getNext() {
return next;
}
public E getValue() {
return e;
}
public void setValue(E e) {
this.e = e;
}
}
单链表
有了节点，来实现一个简单的单链表
**
* 单链表数据结构简单实现
*
* @author jade
*
*/
public class SingleLinkedList<E> {
private Node<E> head = null; // 每个链表都存有一个空值的头结点。
private Node<E> tail = null; // 链表的最后一个结点，尾结点。
private int size = 0; // 当前链表中的节点数目。
/**
* 建立一个空链表（建立其头结点）。
*/
public SingleLinkedList() {
head = new Node<E>();
tail = head;
}
/**
* 在链表的尾部插入数据
* @param e 待插入的数据
* @return
*/
public boolean add(E e) {
Node<E> node = new Node<E>(e); // 将要插入的值封装成一个节点。
tail.setNext(node); // 将待插入结点放到尾结点的下一个结点。
tail = tail.getNext(); // 将新增加的结点设为尾节点。
++size; // 链表大小增1。
return true;
}
/**
*
* @param index 待插入的位置
* @param e 待插入的元素
* @return
*/
public boolean add(int index, E e) {
checkValidateIndex(index);
Node<E> newNode = new Node<E>(e);
Node preNode = null;
if (index > 0) {
preNode = getNode(index - 1);
}else{
preNode = head;
}
newNode.setNext(preNode.getNext());
preNode.setNext(newNode);
return true;
}
/**
* 获取指定位置的结点的值
* @param index 欲获取值的结点的下标
* @return
*/
public E get(int index) {
checkValidateIndex(index);
Node<E> node = getNode(index);
return node.getValue();
}
/**
* 删除指定位置的结点
* @param index 待删除结点的下标
* @return
*/
public boolean remove(int index) {
Node<E> curNode = null;
if (0 == index) {
curNode = head.getNext();
Node<E> nextNode = curNode.getNext();
head.setNext(nextNode);
} else {
checkValidateIndex(index);
curNode = getNode(index); // 获取待删除节点。
Node<E> preNode = getNode(index - 1); // 获取待删除节点的前一个结点。
preNode.setNext(curNode.getNext());
}
curNode.setNext(null); // 将待删除节点的下一结点置空。
return true;
}
/**
* 设置指定位置结点的值。
* @param index 待设置值的结点的下标
* @param e
*/
public void set(int index, E e) {
checkValidateIndex(index);
Node<E> node = getNode(index);
node.setValue(e);
}
/**
* 获取指定位置的结点
* @param index 获取结点的下标
*
*/
private Node<E> getNode(int index) {
checkValidateIndex(index);
Node<E> node = head;
for (int p = 0; p <= index; ++p) {
node = node.getNext();
}
return node;
}
/**
* 验证下标值是否合法，非法时抛出异常。
* @param index 待验证的下标值
* @throws Exception
*
*/
private void checkValidateIndex(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("无效的下标：" + index);
}
}
/**
* 获取链表的大小。
* @return
*/
public int size() {
return size;
}
堆栈和队列是两种特殊的线性表，下面来看一下他们的链式实现
栈（Stack）
java中的Stack是继承Vector的 ：public class Stack<E> extends Vector<E>
下面来看一下Stack的简单实现：
class Stack {
Node top;
/**
* 栈顶元素
* @return
*/
public Node peek() {
if (top != null) {
return top;
}
return null;
}
/**
* 退栈
* @return
*/
public Node pop() {
if (top == null) {
return null;
} else {
Node temp = new Node(top.next);
top = top.next;
return temp;
}
}
/**
* 入栈
* @param n
*/
public void push(Node n) {
if (n != null) {
n.next = top;
top = n;
}
}
}
队列（queue）
下面基于链表实现一个阻塞对列
/**
* 基于链表实现的一个阻塞队列
*
* @author jade
*
*/
public class BlockingQueue {
private int capacity ; // 阻塞队列容量
private List queue = new LinkedList(); // 基于链表实现的一个阻塞队列
public BlockingQueue() {
this(Integer.MAX_VALUE);
}
public BlockingQueue(int capacity) {
this.capacity = capacity;
}
/**
* 入队列
*
* @param item
* @throws InterruptedException
*/
public synchronized void enqueue(Object item) throws InterruptedException {
while (this.queue.size() == this.capacity) {
wait();
}
if (this.queue.size() == 0) {
notifyAll();
}
this.queue.add(item);
}
/**
* 出队列
*
* @return
* @throws InterruptedException
*/
public synchronized Object dequeue() throws InterruptedException {
while (this.queue.size() == 0) {
wait();
}
if (this.queue.size() == this.capacity) {
notifyAll();
}
return this.queue.remove(0);
}
}