雙向鏈表：就是有雙向指針，即雙向的鏈域。\x0d\x0a鏈結(jié)點(diǎn)的結(jié)構(gòu)：\x0d\x0a┌────┬────┬────────┐\x0d\x0a│ data │ next │ previous │\x0d\x0a└────┴────┴────────┘\x0d\x0a雙向鏈表不必是雙端鏈表(持有對(duì)最后一個(gè)鏈結(jié)點(diǎn)的引用)，雙端鏈表插入時(shí)是雙向的。\x0d\x0a有兩條鏈：一條從頭到尾，一條從尾到頭，刪除遍歷時(shí)也是雙向的。\x0d\x0a/**\x0d\x0a * 雙向鏈表\x0d\x0a */\x0d\x0apublic class DoublyLinkedList {\x0d\x0a private Link head; //首結(jié)點(diǎn)\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()) {//為空時(shí)，第1次插入的新結(jié)點(diǎn)為尾結(jié)點(diǎn)\x0d\x0a rear = newLink;\x0d\x0a } else {\x0d\x0a head.previous = newLink; //舊頭結(jié)點(diǎn)的上結(jié)點(diǎn)等于新結(jié)點(diǎn)\x0d\x0a }\x0d\x0a newLink.next = head; //新結(jié)點(diǎn)的下結(jié)點(diǎn)舊頭結(jié)點(diǎn)\x0d\x0a head = newLink; //賦值后，頭結(jié)點(diǎn)的下結(jié)點(diǎn)是舊頭結(jié)點(diǎn)，上結(jié)點(diǎn)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; //賦值后，尾結(jié)點(diǎn)的上結(jié)點(diǎn)是舊尾結(jié)點(diǎn)，下結(jié)點(diǎn)null\x0d\x0a }\x0d\x0a public T deleteHead() {//刪除 鏈頭\x0d\x0a if (isEmpty()) return null;\x0d\x0a Link temp = head;\x0d\x0a head = head.next; //變更首結(jié)點(diǎn)，為下一結(jié)點(diǎn)\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; //變更尾結(jié)點(diǎn)，為上一結(jié)點(diǎn)\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 //中間的非兩端的結(jié)點(diǎn)，要移除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() {//從頭開(kāi)始遍歷\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() {//從尾開(kāi)始遍歷\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 {//鏈結(jié)點(diǎn)\x0d\x0a T data; //數(shù)據(jù)域\x0d\x0a Link next; //后繼指針，結(jié)點(diǎn) 鏈域\x0d\x0a Link previous; //前驅(qū)指針，結(jié)點(diǎn) 鏈域\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}
創(chuàng)新互聯(lián)公司專(zhuān)注于昔陽(yáng)網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供昔陽(yáng)營(yíng)銷(xiāo)型網(wǎng)站建設(shè)，昔陽(yáng)網(wǎng)站制作、昔陽(yáng)網(wǎng)頁(yè)設(shè)計(jì)、昔陽(yáng)網(wǎng)站官網(wǎng)定制、小程序制作服務(wù)，打造昔陽(yáng)網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供昔陽(yáng)網(wǎng)站排名全網(wǎng)營(yíng)銷(xiāo)落地服務(wù)。
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: 返回一個(gè)Set，其中每個(gè)元素為位置信息，在該位置處的鏈表元素值為極大值
//極大值是指該元素不小于其直接前驅(qū)及直接后繼元素
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
曾經(jīng)自己編過(guò),好像...貼給你了..
定義接口：
//Deque.java
package dsa; //根據(jù)自己的程序位置不同
public interface Deque {
public int getSize();//返回隊(duì)列中元素?cái)?shù)目
public boolean isEmpty();//判斷隊(duì)列是否為空
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();//遍歷
}
雙向鏈表實(shí)現(xiàn)：
//Deque_DLNode.java
/*
* 基于雙向鏈表實(shí)現(xiàn)雙端隊(duì)列結(jié)構(gòu)
*/
package dsa;
public class Deque_DLNode implements Deque {
protected DLNode header;//指向頭節(jié)點(diǎn)（哨兵）
protected DLNode trailer;//指向尾節(jié)點(diǎn)（哨兵）
protected int size;//隊(duì)列中元素的數(shù)目
//構(gòu)造函數(shù)
public Deque_DLNode() {
header = new DLNode();
trailer = new DLNode();
header.setNext(trailer);
trailer.setPrev(header);
size = 0;
}
//返回隊(duì)列中元素?cái)?shù)目
public int getSize()
{ return size; }
//判斷隊(duì)列是否為空
public boolean isEmpty()
{ return (0 == size) ? true : false; }
//取首元素（但不刪除）
public Object first() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊(duì)列為空");
return header.getNext().getElem();
}
//取末元素（但不刪除）
public Object last() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊(duì)列為空");
return trailer.getPrev().getElem();
}
//在隊(duì)列前端插入新節(jié)點(diǎn)
public void insertFirst(Object obj) {
DLNode second = header.getNext();
DLNode first = new DLNode(obj, header, second);
second.setPrev(first);
header.setNext(first);
size++;
}
//在隊(duì)列后端插入新節(jié)點(diǎn)
public void insertLast(Object obj) {
DLNode second = trailer.getPrev();
DLNode first = new DLNode(obj, second, trailer);
second.setNext(first);
trailer.setPrev(first);
size++;
}
//刪除首節(jié)點(diǎn)
public Object removeFirst() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊(duì)列為空");
DLNode first = header.getNext();
DLNode second = first.getNext();
Object obj = first.getElem();
header.setNext(second);
second.setPrev(header);
size--;
return(obj);
}
//刪除末節(jié)點(diǎn)
public Object removeLast() throws ExceptionQueueEmpty {
if (isEmpty())
throw new ExceptionQueueEmpty("意外：雙端隊(duì)列為空");
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();
}
}
重慶分公司
重慶分公司
