① 在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();
}
}
② 用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單向鏈表改成雙向鏈表
一、JAVA單向鏈表的操作（增加節點、查找節點、刪除節點）
classLink{//鏈表類
classNode{//保存每一個節點，此處為了方便直接定義成內部類
privateStringdata;//節點的內容
privateNodenext;//保存下一個節點
publicNode(Stringdata){//通過構造方法設置節點內容
this.data=data;
}
publicvoidadd(Nodenode){//增加節點
if(this.next==null){//如果下一個節點為空，則把新節點加入到next的位置上
this.next=node;
}else{//如果下一個節點不為空，則繼續找next
this.next.add(node);
}
}
publicvoidprint(){//列印節點
if(this.next!=null){
System.out.print(this.data+"-->");
this.next.print();
}else{
System.out.print(this.data+"
");
}
}
publicbooleansearch(Stringdata){//內部搜索節點的方法
if(this.data.equals(data)){
returntrue;
}
if(this.next!=null){
returnthis.next.search(data);
}else{
returnfalse;
}
}
publicvoiddelete(Nodeprevious,Stringdata){//內部刪除節點的方法
if(this.data.equals(data)){
previous.next=this.next;
}else{
if(this.next!=null){
this.next.delete(this,data);
}
}
}
}
privateNoderoot;//定義頭節點
publicvoidaddNode(Stringdata){//根據內容添加節點
NodenewNode=newNode(data);//要插入的節點
if(this.root==null){//沒有頭節點，則要插入的節點為頭節點
this.root=newNode;
}else{//如果有頭節點，則調用節點類的方法自動增加
this.root.add(newNode);
}
}
publicvoidprint(){//展示列表的方法
if(root!=null){//當鏈表存在節點的時候進行展示
this.root.print();
}
}
publicbooleansearchNode(Stringdata){//在鏈表中尋找指定內容的節點
returnroot.search(data);//調用內部搜索節點的方法
}
publicvoiddeleteNode(Stringdata){//在鏈表中刪除指定內容的節點
if(root.data.equals(data)){//如果是頭節點
if(root.next!=null){
root=root.next;
}else{
root=null;
}
}else{
root.next.delete(this.root,data);
}
}
}二、雙向鏈表的簡單實現
publicclassDoubleLink<T>{
/**
*Node<AnyType>類定義了雙向鏈表中節點的結構，它是一個私有類，而其屬性和構造函數都是公有的，這樣，其父類可以直接訪問其屬性
*而外部類根本不知道Node類的存在。
*
*@authorZHB
*
*@param<T>
*類型
*@paramData
*是節點中的數據
*@parampre
*指向前一個Node節點
*@paramnext
*指向後一個Node節點
*/
privateclassNode<T>{
publicNode<T>pre;
publicNode<T>next;
publicTdata;
publicNode(Tdata,Node<T>pre,Node<T>next){
this.data=data;
this.pre=pre;
this.next=next;
}
publicNode(){
this.data=null;
this.pre=null;
this.next=null;
}
}
//下面是DoubleLinkedList類的數據成員和方法
privateinttheSize;
privateNode<T>Header;
privateNode<T>Tail;
/*
*構造函數我們構造了一個帶有頭、尾節點的雙向鏈表頭節點的Next指向尾節點為節點的pre指向頭節點鏈表長度起始為0。
*/
publicDoubleLink(){
theSize=0;
Header=newNode<T>(null,null,null);
Tail=newNode<T>(null,Header,null);
Header.next=Tail;
}
publicvoidadd(Titem){
Node<T>aNode=newNode<T>(item,null,null);
Tail.pre.next=aNode;
aNode.pre=Tail.pre;
aNode.next=Tail;
Tail.pre=aNode;
theSize++;
}
publicbooleanisEmpty(){
return(this.theSize==0);
}
publicintsize(){
returnthis.theSize;
}
publicTgetInt(intindex){
if(index>this.theSize-1||index<0)
();
Node<T>current=Header.next;
for(inti=0;i<index;i++){
current=current.next;
}
returncurrent.data;
}
publicvoidprint(){
Node<T>current=Header.next;
while(current.next!=null){
System.out.println(current.data.toString());
current=current.next;
}
}
publicstaticvoidmain(String[]args){
DoubleLink<String>dLink=newDoubleLink<String>();
dLink.add("zhb");
dLink.add("zzb");
dLink.add("zmy");
dLink.add("zzj");
System.out.println("size:"+dLink.size());
System.out.println("isEmpty?:"+dLink.isEmpty());
System.out.println("3:"+dLink.getInt(2));
dLink.print();
}
}
④ JAVA中LinkedList的底層實現是鏈表還是隊列
是鏈表實現，通過引用來找到前面或後面的對象，所以相對來說LinkedList插入、刪除操作比較快，查找較慢，是雙向鏈表。
⑤ java單線鏈表、雙向鏈表及循環鏈表中插入某節點,和刪除某節點的演算法（可能是頭結點、中間節點、尾節點）
API里有現成的，直接用好了
java.util.List
remove
E remove(int index)移除列表中指定位置的元素（可選操作）。將所有的後續元素向左移動（將其索引減 1）。返回從列表中移除的元素。
參數：
index - 要移除的元素的索引
返回：
以前在指定位置的元素
拋出：
UnsupportedOperationException - 如果列表不支持 remove 操作
IndexOutOfBoundsException - 如果索引超出范圍 (index < 0 || index >= size())
remove
boolean remove(Object o)從此列表中移除第一次出現的指定元素（如果存在）（可選操作）。如果列表不包含元素，則不更改列表。更確切地講，移除滿足 (o==null ? get(i)==null : o.equals(get(i))) 的最低索引 i 的元素（如果存在這樣的元素）。如果此列表已包含指定元素（或者此列表由於調用而發生更改），則返回 true。
指定者：
介面 Collection<E> 中的 remove
參數：
o - 要從該列表中移除的元素，如果存在的話
返回：
如果列表包含指定的元素，則返回 true
拋出：
ClassCastException - 如果指定元素的類型和此列表不兼容（可選）
NullPointerException - 如果指定的元素是 null，並且此列表不允許 null 元素（可選）
UnsupportedOperationException - 如果列表不支持 remove 操作
⑥ java怎麼用鏈表實現
在數據結構中經常看見的一個基本概念-鏈表。
鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。
在Java中，對於鏈表的實現都是基於引用數據類型操作的。實現大致如下：
定義節點類Node，節點的概念很重要，一個鏈表是由各各節點連接在一起組成的。在節點類Node中定義節點內容及指向下一節點的引用，再增加一個添加節點的方法即可完成鏈表實現。
鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。在執行效率上，相比數組而言，鏈表插入快查找慢，開發中得根據實際業務使用。
⑦ 用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。這里就不重復了。