重温数据结构之双向链表：
package com.lin.link; /** * 类说明 :双向链表 */ public class DoubleLinkedList { // 节点类Node private static class Node{ Object value; Node prev=this; Node next=this; Node(Object v){ value=v; } @Override public String toString() { // TODO Auto-generated method stub return value.toString(); } } private Node head=new Node(null);// 头节点 private int size;// 链表大小 // 以下是接口方法 public boolean addFirst(Object o){ addAfter(new Node(o), head); return true; } public boolean addLast(Object o){ addBefore(new Node(o), head); return true; } public boolean add(Object o){ return addLast(o); } public boolean add(int index,Object o){ addBefore(new Node(o), getNode(index)); return true; } public boolean remove(int index){ removeNode(getNode(index)); return true; } public boolean removeFirst() { removeNode(head.next); return true; } public boolean removeLast() { removeNode(head.prev); return true; } public Object get(int index){ return getNode(index).value; } public int size(){ return size; } @Override public String toString() { StringBuffer stringBuffer=new StringBuffer("["); Node node=head; for(int i=0;i<size;i++){ node=node.next; if(i>0) stringBuffer.append(", "); stringBuffer.append(node.value); } stringBuffer.append("]"); return stringBuffer.toString(); } //以下是实现方法 private Node getNode(int index){ if(index<0||index>=size) throw new IndexOutOfBoundsException(); Node node=head.next; for (int i = 0; i < index; i++) { node=node.next; } return node; } private void addBefore(Node newNode,Node node){ newNode.next=node; newNode.prev=node.prev; newNode.next.prev=newNode; newNode.prev.next=newNode; size++; } private void addAfter(Node newNode,Node node){ newNode.prev=node; newNode.next=node.next; newNode.next.prev=newNode; newNode.prev.next=newNode; size++; } private void removeNode(Node node){ node.prev.next=node.next; node.next.prev=node.prev; node.prev=null; node.next=null; size--; } public static void main(String[] args) { DoubleLinkedList dll=new DoubleLinkedList(); //添加 dll.add("小明"); dll.add("小李"); dll.add("小红"); System.out.println(dll.size+" : "+dll); //添加到最前 dll.addFirst("小芳"); System.out.println(dll.size+" : "+dll); //添加到最后，同添加 dll.addLast("小王"); System.out.println(dll.size+" : "+dll); //添加到指定位置 dll.add(4, "小林"); System.out.println(dll.size+" : "+dll); //移除最前的 dll.removeFirst(); System.out.println(dll.size+" : "+dll); //移除最后的 dll.removeLast(); System.out.println(dll.size+" : "+dll); //移除指定位置上的 dll.remove(2); System.out.println(dll.size+" : "+dll); //返回指定位置上的元素 System.out.println(dll.get(1)); } }