单向链表只能从一个方向遍历链表，即只能查找结点的下一个结点（后继结点），而不能查找结点的上一个结点（前驱结点）。鉴于上述问题，引入了双向链表。由于双向循环链表包含双向链表的所有功能操作。因此，我们只讲述双向循环链表。
与单向链表不同，双向链表的结点构造如下图所示。即一个结点由三个部分组成，数据域DATA，左指针域pre和右指针域next。其中，数据域用来存放结点数据信息，左指针域用来指向前驱结点，右指针域用来指向后继结点。
代码如下：
package com.qdcz.breadth.demo;
/** * * <p>Title: TwoLinke</p> * <p>Description: 双向链表实现类</br> * <a href="http://blog.csdn.net/basycia/article/details/51839221">详情资料</a> * </p> * <p>Company: 奇点创智</p> * <p>Version: 1.0</p> * @author Administrator * @date 2017年6月6日 下午1:47:31 */public class TwoLinke { public static void main(String[] args) { QuNo node=new QuNo(); node.add("aaa"); node.add("ddd"); node.add("ccc"); System.out.println(node); node.addFirst("BBB"); System.out.println(node); node.addLast("AAA"); System.out.println(node); node.add("DDD", 4); System.out.println(node); node.removeFirst(); System.out.println(node); node.removeLast(); System.out.println(node); node.remove(3); System.out.println(node); System.out.println(node.get(2)); }}class QuNo{ private static class Node1{ Object value; Node1 prev=this; Node1 next=this; public Node1(Object value) { super(); this.value = value; } @Override public String toString() { return "Node1 [value=" + value + "]"; } } private Node1 head=new Node1(null); private int size; public boolean addFirst(Object o){ addAfter(new Node1(o),head); return true; } public boolean addLast(Object o){ addBefore(new Node1(o),head); return true; } public boolean add(Object o){ return addLast(o); } public boolean add(Object o,int index){ addBefore(new Node1(o),getNode1(index)); return true; } public boolean remove(int index){ removeNode1(getNode1(index)); return true; } public boolean removeFirst(){ removeNode1(head.next); return true; } public boolean removeLast(){ removeNode1(head.prev); return true; } public Object get(int index){ return getNode1(index).value; } public int size(){ return size; } public String toString(){ StringBuffer sb=new StringBuffer("["); Node1 node1=head; for (int i = 0; i <size; i++) { node1=node1.next; if(i>0)sb.append(","); sb.append(node1.value); } sb.append("]"); return sb.toString(); } private void removeNode1(Node1 node1) { node1.prev.next=node1.next; node1.next.prev=node1.prev; node1.prev=null; node1.next=null; size++; } private Node1 getNode1(int index) { if(index<0||index>=size)throw new IndexOutOfBoundsException(); Node1 node=head.next; for (int i = 0; i <index; i++) { node=node.next; } return node; } private void addBefore(Node1 node1, Node1 head2) { node1.next=head2; node1.prev=head2.prev; node1.next.prev=node1; node1.prev.next=node1; size++; } private void addAfter(Node1 node1, Node1 head2) { node1.prev=head2; node1.next=head2.next; node1.prev.next=node1; node1.next.prev=node1; size++; }}
转载于:https://www.cnblogs.com/1x-zfd50/p/6959153.html
相关资源：多线程实现双向链表增删改