雙向鏈表

Question

//我有一個單鏈表，看起來像這樣

node head = new Node(); 
head.info = 3; 
head.next = new Node(); 
head.next.info = 6(); 
head.next.next = new Node(); 
head.next.next.info = 9; 
head.next.next.next = null; 

//我怎麼會寫一個雙向鏈表？

class Double Node 
{ 
    info; 
    doubleNode prev; 
    doubleNode next; 
} 

Answer 1

這將是想法：

node head = new Node(); 
head.info = 3; 
node prev, actual, next; 
prev = head; 
actual.prev = prev; 
actual.info = 6; 
actual = actual.next = new Node(); 
actual.prev = prev; 
actual = actual.next = new Node(); 
actual.info = 9; 
... 

假設你將不得不在你的榜樣的行爲，你可以用函數自動執行它，在C＃中會是這樣的：

function GetDoubleLinkedList(Node head, int from, int end, int jumps) 
{ 
    head.info = from; 
    node prev = head, actual, next; 
    for(var i = from+jumps; i <= end; i+=jumps) 
    { 
     actual.prev = prev; 
     actual.info = i; 
     actual = actual.next = new Node(); 
    } 
    actual.info = end; 
    return head; 
} 

//... 
//then you can do 
node head = new Node(); 
head = GetDoubleLinkedList(head, 3, 9, 3); 
//... 

Answer 2

雙鏈表像單鏈表，只是它們在結構聲明中有兩個指針

一前一指針和下一指針

對於執行樣本見this link

Answer 3

這裏是一個DoubleLinkedList的在Java中實現（有一些例子，可以幫助沿着你瞭解它是如何工作的）：

public class Node { 
    public int value; 
    public Node prev; 
    public Node next; 

    public Node(int value) { 
     this.value = value; 
     this.prev = null; 
    } 

    public Node(int value, Node prev) { 
     this.value = value; 
     this.prev = prev; 
    } 

    public Node add(int value) { 
     if(this.next == null) { 
      this.next = new Node(value, this); 
     } else { 
      this.next.add(value); 
     } 
     return this; 
    } 

    public Node last() { 
     if(this.next == null) { 
      return this; 
     } else { 
      return this.next.last(); 
     } 
    } 

    public String toString() { 
     String out = value+" "; 
     if(this.next != null) { 
      out += this.next.toString(); 
     } 
     return out; 
    } 

    public static void main(String...arg) { 
     Node list = (new Node(3)).add(6).add(5).add(9); 

     System.out.println(list.toString()); 
     //Output:3 6 5 9 
     System.out.println(list.last().toString()); 
     //Output:9 
     System.out.println(list.last().prev.prev.toString()); 
     //Output:6 5 9 
    } 
} 

Answer 4

以下是創建雙鏈表並向其添加節點的部分。 您可以根據需要添加刪除和插入功能來更新它。

class Node{ 
    Node prev; 
    Node next; 
    int value; 

    public Node(int value) { 
     this.value = value; 
    } 
} 

class DoubleLinkedList{ 
    Node head; 
    Node tail; 

    public DoubleLinkedList(Node head) { 
     this.head = head; 
     this.tail = head; 
     head.next = null; 
     head.prev = null; 
    } 

    public void addNode(Node node){ 
     tail.next = node; 
     node.prev = tail; 
     tail = node; 
    } 
} 

public class Main { 
    public static void main(String args[]){ 
     Node head= new Node(3); 
     DoubleLinkedList list = new DoubleLinkedList(head); 
     list.addNode(new Node(5)); 
     list.addNode(new Node(6)); 
     list.addNode(new Node(7)); 
     list.addNode(new Node(8)); 
    } 
} 

Answer 5

您可以使用以下DoubleLinkedList類。

public class DoubleLinkedList<T> 
{ 
    Node<T> start; 
    Node<T> end; 

    public void AddFirst(T dataToAdd) 
    { 
     Node<T> tmp = new Node<T>(dataToAdd); 
     if (start == null) 
     { 
      start = tmp; 
      end = start; 
      return; 
     } 
     start.previous = tmp; 
     tmp.next = start; 
     start = tmp; 


     if (start.next == null) 
     { 
      end = start; 
     } 
    } 

    public void AddLast(T dataToAdd) 
    { 
     if (start == null) 
     { 
      AddFirst(dataToAdd); 
      return; 
     } 
     Node<T> tmp = new Node<T>(dataToAdd); 
     end.next = tmp; 
     tmp.previous = end; 
     end = tmp; 
    } 

    public T RemoveFirst() 
    { 
     if (start == null) return default(T); 

     T saveVal = start.data; 
     start = start.next; 
     start.previous = null; 
     if (start == null) end = null; 

     return saveVal; 
    } 

    public T RemoveLast() 
    { 
     if (start == null) return default(T); 

     T saveVal = end.data; 
     end = end.previous; 
     end.next = null; 
     if (start == null) end = null; 

     return saveVal; 
    } 


    public void PrintAll() 
    { 
     Node<T> tmp = start; 
     while (tmp != null) 
     { 
      Console.WriteLine(tmp.data.ToString()); 
      tmp = tmp.next; 
     } 
    } 
} 

，並使用以下節點類

class Node<T> 
{ 
    public T data; 
    public Node<T> next; 
    public Node<T> previous; 

    public Node(T newData) 
    { 
     data = newData; 
     next = null; 
     previous = null; 

    } 
}