双向链表：就是有双向指针，即双向的链域。\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}
创新互联公司专注于昔阳网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供昔阳营销型网站建设，昔阳网站制作、昔阳网页设计、昔阳网站官网定制、小程序制作服务，打造昔阳网络公司原创品牌,更为您提供昔阳网站排名全网营销落地服务。
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
曾经自己编过,好像...贴给你了..
定义接口：
//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();
}
}
