双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
代码如下：
package seqlist.doublelinked; public class DoubleLinkedList { private int size; private Node head; private Node tail; //增 public void addFirst(int val){ Node node=new Node(null,val,head); if(head==null){ tail=node; }else { head.prev=node; } head=node; size++; } public void addLast(int val){ Node node=new Node(tail,val,null); if(tail==null){ head=node; }else { tail.next=node; } tail=node; size++; } public void addIndex(int index,int val){ if(index<0||index>size){ System.out.println("add index illegal!"); }else if(index==0){ addFirst(val); }else if(index==size){ addLast(val); }else { Node prev=node(index-1); Node node=new Node(prev,val,prev.next); prev.next.prev=node; prev.next=node; size++; } } //查 public int get(int index){ if(rangeIndex(index)){ return node(index).val; }else { System.out.println("get index illegal!"); return -1; } } //判断是否存在 public boolean isExist(int val){ for (Node x=head;x!=null;x=x.next) { if(x.val==val){ return true; } } return false; } //改 public void change(int index,int val){ if(rangeIndex(index)){ Node oldNode=node(index); oldNode.val=val; }else { System.out.println("get index illegal!"); } } //删 public void removeIndex(int index){ if (rangeIndex(index)){ Node node=node(index); unLink(node); }else { System.out.println("remove index illegal!"); } } public void removeFirst(){ removeIndex(0); } public void removeLast(){ removeIndex(size-1); } public void removeValOnce(int val){ for(Node x=head;x!=null;x=x.next){ if(x.val==val){ unLink(x); } } } public void removeValeAll(int val){ for (Node x=head;x!=null;){ if(x.val==val){ Node node=x.next; unLink(x); x=node; }else { x=x.next; } } } //删除指定节点 public void unLink(Node node){ //分治思想 Node prev= node.prev; Node next= node.next; if(prev==null){ head=next; }else { prev.next=next; node.prev=null; } if(next==null){ tail=prev; }else { next.prev=prev; node.next=null; } size--; } //判断合法性 public boolean rangeIndex(int index){ if(index<0||index>=size){ return false; }else { return true; } } //得到索引节点 public Node node(int index){ Node ret=null; if(index<(size>>1)){ ret=head; for (int i = 0; i < index; i++) { ret=ret.next; } }else { ret=tail; for (int i = size-1; i > index; i++) { ret=ret.prev; } } return ret; } //输出 public String toString(){ String ret=""; Node node=head; while (node!=null){ ret+=node.val; ret+="->"; node=node.next; } ret+="null"; return ret; } } class Node{ Node prev; int val; Node next; public Node(int val){ this.val=val; } public Node(Node prev,int val,Node next){ this.prev=prev; this.val=val; this.next=next; } }
引用方法如下：
package seqlist; import seqlist.doublelinked.DoubleLinkedList; public class Test { public static void main(String[] args) { DoubleLinkedList doubleLinkedList=new DoubleLinkedList(); doubleLinkedList.addFirst(1); doubleLinkedList.addLast(3); doubleLinkedList.addLast(4); doubleLinkedList.addIndex(1,2); //增 1->2->3->4->null System.out.println(doubleLinkedList); //查 2 System.out.println(doubleLinkedList.get(1)); //是否存在 true System.out.println(doubleLinkedList.isExist(1)); //改 10->2->3->4->null doubleLinkedList.change(0,10); System.out.println(doubleLinkedList); //删 3->null doubleLinkedList.removeFirst(); doubleLinkedList.removeLast(); doubleLinkedList.removeIndex(0); System.out.println(doubleLinkedList); //增 1->2->3->4->5->5->null doubleLinkedList.addFirst(2); doubleLinkedList.addFirst(1); doubleLinkedList.addLast(4); doubleLinkedList.addIndex(4,5); doubleLinkedList.addLast(5); System.out.println(doubleLinkedList); //删 3->null doubleLinkedList.removeFirst(); doubleLinkedList.removeValOnce(2); doubleLinkedList.removeValeAll(5); doubleLinkedList.removeLast(); System.out.println(doubleLinkedList); } }
依据以上输入结果如下：
编辑
