在Java中如何实现双向链表?

双向链表：就是有双向指针，即双向的链域。\x0d\x0a链结点的结构：\x0d\x0a┌────┬────┬────────┐\x0d\x0a│ data │ next │ previous │\x0d\x0a└────┴────┴────────┘\x0d\x0a双向链表不必是双端链表(持有对最后一个链结点的引用)，双端链表插入时是双向的。\x0d\x0a有两条链：一条从头到尾，一条从尾到头，删除遍历时也是双向的。\x0d\x0a/**\x0d\x0a * 双向链表\x0d\x0a */\x0d\x0apublic class DoublyLinkedList {\x0d\x0a private Link head; //首结点\x0d\x0a private Link rear; //尾部指针\x0d\x0a public DoublyLinkedList() { }\x0d\x0a public T peekHead() {\x0d\x0a if (head != null) {\x0d\x0a return head.data;\x0d\x0a }\x0d\x0a return null;\x0d\x0a }\x0d\x0a public boolean isEmpty() {\x0d\x0a return head == null;\x0d\x0a }\x0d\x0a public void insertFirst(T data) {// 插入 到 链头\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (isEmpty()) {//为空时，第1次插入的新结点为尾结点\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a head.previous = newLink; //旧头结点的上结点等于新结点\x0d\x0a }\x0d\x0a newLink.next = head; //新结点的下结点旧头结点\x0d\x0a head = newLink; //赋值后，头结点的下结点是旧头结点，上结点null\x0d\x0a }\x0d\x0a public void insertLast(T data) {//在链尾 插入\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (isEmpty()) {\x0d\x0a head = newLink;\x0d\x0a } else {\x0d\x0a rear.next = newLink;\x0d\x0a }\x0d\x0a newLink.previous = rear;\x0d\x0a rear = newLink; //赋值后，尾结点的上结点是旧尾结点，下结点null\x0d\x0a }\x0d\x0a public T deleteHead() {//删除 链头\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = head;\x0d\x0a head = head.next; //变更首结点，为下一结点\x0d\x0a if (head != null) {\x0d\x0a head.previous = null;\x0d\x0a } else {\x0d\x0a rear = null;\x0d\x0a }\x0d\x0a return temp.data;\x0d\x0a }\x0d\x0a public T deleteRear() {//删除 链尾\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = rear;\x0d\x0a rear = rear.previous; //变更尾结点，为上一结点\x0d\x0a if (rear != null) {\x0d\x0a rear.next = null;\x0d\x0a } else {\x0d\x0a head = null;\x0d\x0a }\x0d\x0a return temp.data;\x0d\x0a }\x0d\x0a public T find(T t) {//从头到尾find\x0d\x0a if (isEmpty()) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a Link find = head;\x0d\x0a while (find != null) {\x0d\x0a if (!find.data.equals(t)) {\x0d\x0a find = find.next;\x0d\x0a } else {\x0d\x0a break;\x0d\x0a }\x0d\x0a }\x0d\x0a if (find == null) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a return find.data;\x0d\x0a }\x0d\x0a public T delete(T t) {\x0d\x0a if (isEmpty()) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a Link current = head;\x0d\x0a while (!current.data.equals(t)) {\x0d\x0a current = current.next;\x0d\x0a if (current == null) {\x0d\x0a return null;\x0d\x0a }\x0d\x0a }\x0d\x0a if (current == head) {\x0d\x0a head = head.next;\x0d\x0a if (head != null) {\x0d\x0a head.previous = null;\x0d\x0a }\x0d\x0a } else if (current == rear) {\x0d\x0a rear = rear.previous;\x0d\x0a if (rear != null) {\x0d\x0a rear.next = null;\x0d\x0a }\x0d\x0a } else {\x0d\x0a //中间的非两端的结点，要移除current\x0d\x0a current.next.previous = current.previous;\x0d\x0a current.previous.next = current.next;\x0d\x0a }\x0d\x0a return current.data;\x0d\x0a }\x0d\x0a public boolean insertAfter(T key, T data) {//插入在key之后, key不存在return false\x0d\x0a if (isEmpty()) {\x0d\x0a return false;\x0d\x0a }\x0d\x0a Link current = head;\x0d\x0a while (!current.data.equals(key)) {\x0d\x0a current = current.next;\x0d\x0a if (current == null) {\x0d\x0a return false;\x0d\x0a }\x0d\x0a }\x0d\x0a Link newLink = new Link(data);\x0d\x0a if (current == rear) {\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a newLink.next = current.next;\x0d\x0a current.next.previous = newLink;\x0d\x0a }\x0d\x0a current.next = newLink;\x0d\x0a newLink.previous = current;\x0d\x0a return true;\x0d\x0a }\x0d\x0a public void displayList4Head() {//从头开始遍历\x0d\x0a System.out.println("List (first--last):");\x0d\x0a Link current = head;\x0d\x0a while (current != null) {\x0d\x0a current.displayLink();\x0d\x0a current = current.next;\x0d\x0a }\x0d\x0a }\x0d\x0a public void displayList4Rear() {//从尾开始遍历\x0d\x0a System.out.println("List (last--first):");\x0d\x0a Link current = rear;\x0d\x0a while (current != null) {\x0d\x0a current.displayLink();\x0d\x0a current = current.previous;\x0d\x0a }\x0d\x0a }\x0d\x0a\x0d\x0a class Link {//链结点\x0d\x0a T data; //数据域\x0d\x0a Link next; //后继指针，结点 链域\x0d\x0a Link previous; //前驱指针，结点 链域\x0d\x0a Link(T data) {\x0d\x0a this.data = data;\x0d\x0a }\x0d\x0a void displayLink() {\x0d\x0a System.out.println("the data is " + data.toString());\x0d\x0a }\x0d\x0a }\x0d\x0a public static void main(String[] args) {\x0d\x0a DoublyLinkedList list = new DoublyLinkedList();\x0d\x0a list.insertLast(1);\x0d\x0a list.insertFirst(2);\x0d\x0a list.insertLast(3);\x0d\x0a list.insertFirst(4);\x0d\x0a list.insertLast(5);\x0d\x0a list.displayList4Head();\x0d\x0a Integer deleteHead = list.deleteHead();\x0d\x0a System.out.println("deleteHead:" + deleteHead);\x0d\x0a list.displayList4Head();\x0d\x0a Integer deleteRear = list.deleteRear();\x0d\x0a System.out.println("deleteRear:" + deleteRear);\x0d\x0a list.displayList4Rear();\x0d\x0a System.out.println("find:" + list.find(6));\x0d\x0a System.out.println("find:" + list.find(3));\x0d\x0a System.out.println("delete find:" + list.delete(6));\x0d\x0a System.out.println("delete find:" + list.delete(1));\x0d\x0a list.displayList4Head();\x0d\x0a System.out.println("----在指定key后插入----");\x0d\x0a list.insertAfter(2, 8);\x0d\x0a list.insertAfter(2, 9);\x0d\x0a list.insertAfter(9, 10);\x0d\x0a list.displayList4Head();\x0d\x0a }\x0d\x0a}

创新互联公司专注于昔阳网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供昔阳营销型网站建设，昔阳网站制作、昔阳网页设计、昔阳网站官网定制、小程序制作服务，打造昔阳网络公司原创品牌,更为您提供昔阳网站排名全网营销落地服务。

Java 双向链表

import java.util.*;

public class DoublyLinkedList {

//overview: a list that is doublylinked

private ListNode firstNode;

private ListNode lastNode;

//constructors:

public DoublyLinkedList(){

//EFFECTS: initialize this to be empty

firstNode = null;

lastNode = null;

}

//methods:

public synchronized void insertAtFront(Object o){

//EFFECTS: add o to the front of this

//MODIFIES: this

if(isEmpty()){

firstNode = lastNode = firstNode.nextNode = firstNode.prevNode = lastNode.nextNode = lastNode.prevNode = new ListNode(o);

}

else{

firstNode = new ListNode(o , firstNode , lastNode);

lastNode.nextNode = firstNode;

}

}

public synchronized void insertAtBack(Object o){

//EFFECTS: add o to the back of this

//MODIFIES: this

if(isEmpty()){

firstNode = lastNode = firstNode.nextNode = firstNode.prevNode = lastNode.nextNode = lastNode.prevNode = new ListNode(o);

}

else{

lastNode = lastNode.nextNode = new ListNode(o , lastNode , firstNode);

firstNode.prevNode = lastNode;

}

}

public synchronized Object removeFromFront() throws EmptyListException{

//EFFECTS: remove the first node of this and return the node

//MODIFIES: this

Object o = null;

if(isEmpty()){

throw new EmptyListException();

}

else{

o = firstNode.data;

if(firstNode == lastNode){

firstNode = lastNode = null;

}

else{

firstNode = firstNode.nextNode;

firstNode.prevNode = lastNode;

firstNode.nextNode = firstNode;

}

}

return o;

}

public synchronized Object removeFromBack() throws EmptyListException{

//EFFECTS: remove the last node of this and return the node

//MODIFIES: this

Object o = null;

if(isEmpty()){

throw new EmptyListException();

}

else{

o = firstNode.data;

if(firstNode == lastNode){

firstNode = lastNode = null;

}

else{

lastNode = lastNode.prevNode;

lastNode.nextNode = firstNode;

firstNode.prevNode = lastNode;

}

}

return o;

}

public synchronized Set LocalMaximum(){

//EFFECTS: 返回一个Set，其中每个元素为位置信息，在该位置处的链表元素值为极大值

//极大值是指该元素不小于其直接前驱及直接后继元素

ListNode current = firstNode;

SetInteger a = null ;

int n = 0;

while(current.nextNode != firstNode){

if(Integer.parseInt(current.data.toString()) = Integer.parseInt(current.prevNode.data.toString())

Integer.parseInt(current.data.toString()) = Integer.parseInt(current.nextNode.data.toString()))

a.add(new Integer(n));

n++;

}

return a;

}

public Iterator iterator(int direction) throws Exception{

//EFFECTS: if direction is 0 return a generator that will produce all elements of this from the first node to the last one

//else if direction is 0 return a generator that will produce all elements of this from the last node to the first one

//REQUIRES: this must not be modified while the generator is in use

if(direction == 0){

return new fl(this);

}

else if(direction == 1){

return new lf(this);

}

else{

throw new Exception("Enter the right direction!");

}

}

//inner class

private static class fl implements Iterator{

//overview: from first to last

private ListNode current;

private DoublyLinkedList y;

//constructors:

public fl(DoublyLinkedList x){

//EFFECTS: initialize this

y = x;

current = y.firstNode;

}

//methods:

public boolean hasNext(){

//EFFECTS: return true if there are more elements else return false

if(current == y.lastNode)

return false;

else

return true;

}

public Object next() throws NoSuchElementException{

//EFFECTS: If there are more results to yield, returns the next result and modifies the state of this to record the yield.

// Otherwise throws NoSuchElementException

if(current == y.lastNode)

throw new NoSuchElementException("DoublyLinkedList.iterator");

else{

current = current.nextNode;

return current;

}

}

public void remove() throws UnsupportedOperationException{

throw new UnsupportedOperationException("DoublyLinkedList.iterator");

}

//end methods

//end constructors

}//end class

private static class lf implements Iterator{

//overview: from last to first

private ListNode current;

private DoublyLinkedList y;

//constructors:

public lf(DoublyLinkedList x){

//EFFECTS: initialize this

y = x;

current = y.lastNode;

}

//methods:

public boolean hasNext(){

//EFFECTS: return true if there are more elements else return false

if(current == y.firstNode)

return false;

else

return true;

}

public Object next() throws NoSuchElementException{

//EFFECTS: If there are more results to yield, returns the next result and modifies the state of this to record the yield.

// Otherwise throws NoSuchElementException

if(current == y.firstNode)

throw new NoSuchElementException("DoublyLinkedList.iterator");

else{

current = current.prevNode;

return current;

}

}

public void remove() throws UnsupportedOperationException{

throw new UnsupportedOperationException("DoublyLinkedList.iterator");

}

//end methods

// end constructors

}//end class

public synchronized boolean isEmpty(){

//EFFECTS: if this is not empty retutn true else return false

return firstNode == null;

}

//end methods

//end constructors

}//end class

class ListNode{

//overview: ListNode is the node of a list

Object data;

ListNode nextNode;

ListNode prevNode;

//constructors:

public ListNode(Object o){

//EFFECTS: initialize this to be a node like(o , null)

this( o , null , null);

}

public ListNode(Object o , ListNode node1 , ListNode node2){

//EFFECTS: initialize this to be a node like(node1 , o , node2)

data = o ;

nextNode = node1;

prevNode = node2;

}

//methods:

Object getObject(){

//EFFECTS: return the object of this

return data;

}

ListNode getNext(){

//EFFECTS: return the next node of this

return nextNode;

}

ListNode getPrev(){

//EFFECTS: return the prev node of this

return prevNode;

}

//end methods

//end constructors

}//end class

class EmptyListException extends RuntimeException {

//constructors:

public EmptyListException(){

//EFFECTS: initialize an EmptyListException

super( "The list is empty" );

}

} // end class

曾经自己编过,好像...贴给你了..

用JAVA语言，编写一个链表类(双向链表),实现插入,删除,查找操作。新手，要俗易懂些，最好自己调适通过。急

定义接口：

//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 {

if (isEmpty())

throw new ExceptionQueueEmpty("意外：双端队列为空");

return trailer.getPrev().getElem();

}

//在队列前端插入新节点

public void insertFirst(Object obj) {

DLNode second = header.getNext();

DLNode first = new DLNode(obj, header, second);

second.setPrev(first);

header.setNext(first);

size++;

}

//在队列后端插入新节点

public void insertLast(Object obj) {

DLNode second = trailer.getPrev();

DLNode first = new DLNode(obj, second, trailer);

second.setNext(first);

trailer.setPrev(first);

size++;

}

//删除首节点

public Object removeFirst() throws ExceptionQueueEmpty {

if (isEmpty())

throw new ExceptionQueueEmpty("意外：双端队列为空");

DLNode first = header.getNext();

DLNode second = first.getNext();

Object obj = first.getElem();

header.setNext(second);

second.setPrev(header);

size--;

return(obj);

}

//删除末节点

public Object removeLast() throws ExceptionQueueEmpty {

if (isEmpty())

throw new ExceptionQueueEmpty("意外：双端队列为空");

DLNode first = trailer.getPrev();

DLNode second = first.getPrev();

Object obj = first.getElem();

trailer.setPrev(second);

second.setNext(trailer);

size--;

return(obj);

}

//遍历

public void Traversal() {

DLNode p = header.getNext();

while (p != trailer) {

System.out.print(p.getElem()+" ");

p = p.getNext();

}

System.out.println();

}

}

名称栏目：java双向链表代码 双向链表js
浏览路径：http://pwwzsj.com/article/dopjopd.html