定义接口：
//Deque.java
package dsa; //根据自己的程序位置不同
public interface Deque {
public int getSize();//返回队列中元素数目
public boolean isEmpty();//判断队列是否为空
public Object first() throws ExceptionQueueEmpty;//取首元素（但不删除）
public Object last() throws ExceptionQueueEmpty;//取末元素（但不删除）
public void insertFirst(Object obj);//将新元素作为首元素插入
public void insertLast(Object obj);//将新元素作为末元素插入
public Object removeFirst() throws ExceptionQueueEmpty;//删除首元素
public Object removeLast() throws ExceptionQueueEmpty;//删除末元素
public void Traversal();//遍历
}
双向链表实现：
//Deque_DLNode.java
/*
* 基于双向链表实现双端队列结构
*/
package dsa;
public class Deque_DLNode implements Deque {
protected DLNode header;//指向头节点（哨兵）
protected DLNode trailer;//指向尾节点（哨兵）
protected int size;//队列中元素的数目
//构造函数
public Deque_DLNode() {
header = new DLNode();
trailer = new DLNode();
header.setNext(trailer);
trailer.setPrev(header);
size = 0;
//返回队列中元素数目
public int getSize()
{ return size; }
//判断队列是否为空
public boolean isEmpty()
{ return (0 == size) ? true : false; }
//取首元素（但不删除）
public Object first() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：双端队列为空");
return header.getNext().getElem();
//取末元素（但不删除）
public Object last() throws ExceptionQueueEmpty {
return trailer.getPrev().getElem();
//在队列前端插入新节点
public void insertFirst(Object obj) {
DLNodesecond = header.getNext();
DLNodefirst = new DLNode(obj, header, second);
second.setPrev(first);
header.setNext(first);
size++;
//在队列后端插入新节点
public void insertLast(Object obj) {
DLNodesecond = trailer.getPrev();
DLNodefirst = new DLNode(obj, second, trailer);
second.setNext(first);
trailer.setPrev(first);
//删除首节点
public Object removeFirst() throws ExceptionQueueEmpty {
DLNodefirst = header.getNext();
DLNodesecond = first.getNext();
Objectobj = first.getElem();
header.setNext(second);
second.setPrev(header);
size--;
return(obj);
//删除末节点
public Object removeLast() throws ExceptionQueueEmpty {
DLNodefirst = trailer.getPrev();
DLNodesecond = first.getPrev();
trailer.setPrev(second);
second.setNext(trailer);
//遍历
public void Traversal() {
DLNodep = header.getNext();
while (p != trailer) {
System.out.print(p.getElem()+" ");
p = p.getNext();
System.out.println();
public class DoubleLinkedList
{
// 节点类Node
private static class Node
Object value;
Node prev = this;
Node next = this;
Node(Object v)
value = v;
public String toString()
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);
public boolean add(Object o)
return addLast(o);
public boolean add(int index, Object o)
addBefore(new Node(o), getNode(index));
public boolean remove(int index)
removeNode(getNode(index));
public boolean removeFirst()
removeNode(head.next);
public boolean removeLast()
removeNode(head.prev);
public Object get(int index)
return getNode(index).value;
public int size()
return size;
StringBuffer s = new StringBuffer("[");
Node node = head;
for (int i = 0; i size; i++)
node = node.next;
if (i 0)
s.append(", ");
s.append(node.value);
s.append("]");
return s.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++)
return node;
private void addBefore(Node newNode, Node node)
newNode.next = node;
newNode.prev = node.prev;
newNode.next.prev = newNode;
newNode.prev.next = newNode;
private void addAfter(Node newNode, Node node)
newNode.prev = node;
newNode.next = node.next;
private void removeNode(Node node)
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
//测试类：
public class Test
public static void main(String[] args)
DoubleLinkedList dll = new DoubleLinkedList();
//添加
dll.add("张三");
dll.add("李四");
dll.add("王五");
System.out.println(dll);
//添加到最前
dll.addFirst("孙七");
//添加到最后,同添加
dll.addLast("赵六");
//添加到指定位置
//移除最前的
dll.removeFirst();
//移除最后的
dll.removeLast();
//移除指定位置上的
//返回指定位置上的元素
System.out.println(dll.get(1));
public boolean putAfter(Object obj,DoublyListNode node)//有可能找不到obj,所以我返回boolean
DoublyListNode current = head;
while(head.obj!=obj){
current = current.next;
if(current==null)
return false;
if(current==tail){
tail = node;
}else{
node.next = current.next;
current.next.previous = node;
node.previous = current;
current.next =node;
public DoublyListNode removeafter(Object obj){//返回了选中的节点
while(current.obj!=obj)
if(current == null)
return null;
if(current==head)
head = current.next;
else
current.previous.next = current.next;
if(current == tail)
tail = current.previous;
current.next.previous = current.previous;
return current;
双向链表：就是有双向指针,即双向的链域.
链结点的结构：
┌────┬────┬────────┐
│ data │ next │ previous │
└────┴────┴────────┘
双向链表不必是双端链表(持有对最后一个链结点的引用),双端链表插入时是双向的.
有两条链：一条从头到尾,一条从尾到头,删除遍历时也是双向的.
/**
* 双向链表
public class DoublyLinkedListt {
private Linkt head; //首结点
private Linkt rear; //尾部指针
public DoublyLinkedList() { }
public T peekHead() {
if (head != null) {
return head.data;
public boolean isEmpty() {
return head == null;
public void insertFirst(T data) {// 插入 到 链头
Linkt newLink = new Linkt(data);
if (isEmpty()) {//为空时,第1次插入的新结点为尾结点
rear = newLink;
} else {
head.previous = newLink; //旧头结点的上结点等于新结点
newLink.next = head; //新结点的下结点旧头结点
head = newLink; //赋值后,头结点的下结点是旧头结点,上结点null
public void insertLast(T data) {//在链尾 插入
if (isEmpty()) {
head = newLink;
rear.next = newLink;
newLink.previous = rear;
rear = newLink; //赋值后,尾结点的上结点是旧尾结点,下结点null
public T deleteHead() {//删除 链头
if (isEmpty()) return null;
Linkt temp = head;
head = head.next; //变更首结点,为下一结点
head.previous = null;
rear = null;
return temp.data;
public T deleteRear() {//删除 链尾
Linkt temp = rear;
rear = rear.previous; //变更尾结点,为上一结点
if (rear != null) {
rear.next = null;
head = null;
public T find(T t) {//从头到尾find
Linkt find = head;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
break;
if (find == null) {
return find.data;
public T delete(T t) {
Linkt current = head;
while (!current.data.equals(t)) {
if (current == null) {
if (current == head) {
head = head.next;
} else if (current == rear) {
rear = rear.previous;
//中间的非两端的结点,要移除current
return current.data;
public boolean insertAfter(T key, T data) {//插入在key之后, key不存在return false
while (!current.data.equals(key)) {
if (current == rear) {
newLink.next = current.next;
current.next.previous = newLink;
current.next = newLink;
newLink.previous = current;
System.out.println("List (first--last):");
while (current != null) {
System.out.println("List (last--first):");
Linkt current = rear;
current = current.previous;
class Linkt {//链结点
T data; //数据域
Linkt next; //后继指针,结点 链域
Linkt previous; //前驱指针,结点 链域
Link(T data) {
this.data = data;
System.out.println("the data is " + data.toString());
public static void main(String[] args) {
DoublyLinkedListinteger list = new DoublyLinkedListinteger();
list.insertLast(1);
Integer deleteHead = list.deleteHead();
System.out.println("deleteHead:" + deleteHead);
Integer deleteRear = list.deleteRear();
System.out.println("deleteRear:" + deleteRear);
System.out.println("delete find:" + list.delete(1));
System.out.println("----在指定key后插入----");
以上就是土嘎嘎小编为大家整理的双向链表查找代码java相关主题介绍,如果您觉得小编更新的文章只要能对粉丝们有用,就是我们最大的鼓励和动力,不要忘记讲本站分享给您身边的朋友哦！！