1. 在java中如何實現雙向鏈表
雙向鏈表：就是有雙向指針，即雙向的鏈域。
鏈結點的結構：
┌────┬────┬────────┐
│ data │ next │ previous │
└────┴────┴────────┘
雙向鏈表不必是雙端鏈表(持有對最後一個鏈結點的引用)，雙端鏈表插入時是雙向的。
有兩條鏈：一條從頭到尾，一條從尾到頭，刪除遍歷時也是雙向的。
/**
* 雙向鏈表
*/
public class DoublyLinkedList<t> {
private Link<t> head; //首結點
private Link<t> rear; //尾部指針
public DoublyLinkedList() { }
public T peekHead() {
if (head != null) {
return head.data;
}
return null;
}
public boolean isEmpty() {
return head == null;
}
public void insertFirst(T data) {// 插入 到 鏈頭
Link<t> newLink = new Link<t>(data);
if (isEmpty()) {//為空時，第1次插入的新結點為尾結點
rear = newLink;
} else {
head.previous = newLink; //舊頭結點的上結點等於新結點
}
newLink.next = head; //新結點的下結點舊頭結點
head = newLink; //賦值後，頭結點的下結點是舊頭結點，上結點null
}
public void insertLast(T data) {//在鏈尾 插入
Link<t> newLink = new Link<t>(data);
if (isEmpty()) {
head = newLink;
} else {
rear.next = newLink;
}
newLink.previous = rear;
rear = newLink; //賦值後，尾結點的上結點是舊尾結點，下結點null
}
public T deleteHead() {//刪除 鏈頭
if (isEmpty()) return null;
Link<t> temp = head;
head = head.next; //變更首結點，為下一結點
if (head != null) {
head.previous = null;
} else {
rear = null;
}
return temp.data;
}
public T deleteRear() {//刪除 鏈尾
if (isEmpty()) return null;
Link<t> temp = rear;
rear = rear.previous; //變更尾結點，為上一結點
if (rear != null) {
rear.next = null;
} else {
head = null;
}
return temp.data;
}
public T find(T t) {//從頭到尾find
if (isEmpty()) {
return null;
}
Link<t> find = head;
while (find != null) {
if (!find.data.equals(t)) {
find = find.next;
} else {
break;
}
}
if (find == null) {
return null;
}
return find.data;
}
public T delete(T t) {
if (isEmpty()) {
return null;
}
Link<t> current = head;
while (!current.data.equals(t)) {
current = current.next;
if (current == null) {
return null;
}
}
if (current == head) {
head = head.next;
if (head != null) {
head.previous = null;
}
} else if (current == rear) {
rear = rear.previous;
if (rear != null) {
rear.next = null;
}
} else {
//中間的非兩端的結點，要移除current
current.next.previous = current.previous;
current.previous.next = current.next;
}
return current.data;
}
public boolean insertAfter(T key, T data) {//插入在key之後, key不存在return false
if (isEmpty()) {
return false;
}
Link<t> current = head;
while (!current.data.equals(key)) {
current = current.next;
if (current == null) {
return false;
}
}
Link<t> newLink = new Link<t>(data);
if (current == rear) {
rear = newLink;
} else {
newLink.next = current.next;
current.next.previous = newLink;
}
current.next = newLink;
newLink.previous = current;
return true;
}
public void displayList4Head() {//從頭開始遍歷
System.out.println("List (first-->last):");
Link<t> current = head;
while (current != null) {
current.displayLink();
current = current.next;
}
}
public void displayList4Rear() {//從尾開始遍歷
System.out.println("List (last-->first):");
Link<t> current = rear;
while (current != null) {
current.displayLink();
current = current.previous;
}
}
class Link<t> {//鏈結點
T data; //數據域
Link<t> next; //後繼指針，結點 鏈域
Link<t> previous; //前驅指針，結點 鏈域
Link(T data) {
this.data = data;
}
void displayLink() {
System.out.println("the data is " + data.toString());
}
}
public static void main(String[] args) {
DoublyLinkedList<integer> list = new DoublyLinkedList<integer>();
list.insertLast(1);
list.insertFirst(2);
list.insertLast(3);
list.insertFirst(4);
list.insertLast(5);
list.displayList4Head();
Integer deleteHead = list.deleteHead();
System.out.println("deleteHead:" + deleteHead);
list.displayList4Head();
Integer deleteRear = list.deleteRear();
System.out.println("deleteRear:" + deleteRear);
list.displayList4Rear();
System.out.println("find:" + list.find(6));
System.out.println("find:" + list.find(3));
System.out.println("delete find:" + list.delete(6));
System.out.println("delete find:" + list.delete(1));
list.displayList4Head();
System.out.println("----在指定key後插入----");
list.insertAfter(2, 8);
list.insertAfter(2, 9);
list.insertAfter(9, 10);
list.displayList4Head();
}
}
2. 用java如何創建一個單鏈表和雙鏈表
單向鏈表
單向鏈表就是通過每個結點的指針指向下一個結點從而鏈接起來的結構。
單向鏈表的初始化：這里我所講的鏈表都是頭結點不參與計算的，也就是說第一個結點都是頭結點後面的第一個結點。所以我要先申明一點，這里我把鏈表的初始化放在了構造函數部分，然後析構函數負責釋放頭結點的內存。
單向鏈表的創建過程：鏈表的創建就是添加結點到鏈表的最後，開始是添加一個結點到head結點後面，然後添加一個結點到上次添加的結點後面，每次新建的結點的指針總是指向NULL指針。從上面的示意圖可以看出，我們需要一個輔助指針一直指向最後一個結點，這個輔助結點就是為了讓每次添加的結點都放置在最後一個位置。
單向鏈表插入結點過程：源代碼中的的插入結點函數我設置了一個指定位置，就是在指定位置插入結點。首先，通過位置變數position讓ptemp結點移動到要插入位置的前一個位置，然後接下來的過程就是和創建鏈表的過程是一樣的，把新建的結點添加到ptemp的後面。這里變數position可以從1到鏈表長度加1，意思就是如果不算頭結點的話有3個結點，那你的position變數就可以從1到4，這是因為ptemp指針可以到第3個結點的位置，所以新建結點的位置就可以到4了。
單向鏈表刪除結點過程：源代碼中的刪除結點函數也有一個指定位置變數，為了刪除指定位置的結點。和插入結點一樣通過變數position把ptemp移動到要刪除結點的前一個位置，然後讓ptemp結點中的指針指向要刪除結點後面的一個結點，也就是ptemp結點的下一個的下一個結點，雖然這個結點可能為空，但是程序還是正常運行。但是這里和插入結點不同的是變數position只能從1到鏈表的長度，是因為ptemp移動到最後一個結點的時候，它的下一個結點為空，所以不不需要參與刪除了。
雙向鏈表
1.聽名字可能就能猜到雙向鏈表就是鏈表結點包含兩個指針，一個指針是指向下一個結點的，另一個指針當然就是指向上一個結點的。
2.雙向鏈表的初始化：由於這里的鏈表頭結點不參與計算，所以頭結點的pPre指針是一直指向NULL指針的。
3.雙向鏈表的創建過程：由於雙向鏈表的每個結點包含兩個指針那麼這個時候我們就要小心處理好每一個指針的指向，要不然會有很多意想不到的錯誤。同樣的，和單向鏈表的創建過程一樣，需要一個輔助指針來指向最後一個結點，然後每新建一個結點，這個結點的pNext指針都是指向NULL指針的，pPre指針指向上一個結點（這是和單向鏈表不同的地方），然後讓上一個指針的pNext指向新建的結點，這樣整個鏈表就連接起來了。
4.雙向鏈表插入結點過程：知道了雙向鏈表的創建過程，那麼插入結點的過程就大同小異 了，有一點需要特別注意的就是這里的變數position范圍也是從1到鏈表長度加1，但是如果待插入的位置是最後一個位置的話，情況就不同了，看到下面的圖我們可以很好的理解，因為沒新建一個結點的時候都需要處理兩個指針，而且新建結點的下一個結點的pPre指針就需要指向這個新建的結點，但是有可能這個新建的結點可能就已經是最後一個結點了，那麼這個時候再執行
ptemp->pNext->pPre=pnew;
這條指令的時候就會報錯了，因為ptemp->pNext已經是個NULL指針了，那空指針哪裡還有pPre呢。因此在程序中要進行一次判斷，看看結點是否是最後一個結點。
5.雙向鏈表刪除結點的過程：要注意的問題和插入結點一樣，看看這個結點是否為NULL。這里就不重復了。
3. 用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();
}
}