鏈接列表如何工作？

Question

我正在閱讀教程，我也查看了所有的谷歌，但我找不到詳細的鏈接列表的工作原理......我對結構/格式非常困惑，我真的希望鏈表對我來說是有意義的，因爲它們聽起來不錯，是一個可調整大小和可修改的數組...下面是我從tut中得到的一些代碼，如果你需要看看我在說什麼。我感到困惑的方法，如追加方式或刪除，他們做了什麼，以及如何尾頭啄在列表工作......這本書剛剛開始用一個例子並沒有給出解釋..

請這方面的幫助混亂..

class ListEntry 
{ 
    int data; 
    ListEntry next; 

    public ListEntry(int d) 
    { 
     data = d; 
     next = null; 
    } 

    public int Data 
    { 
     get{ return data; } 
     set{ data = value; } 
    } 

    public ListEntry Next 
    { 
     get{ return next; } 
     set{ next = value; } 
    } 

    public override string ToString() 
    { 
     return(data.ToString()); 
    } 
} 


class TestProgram 
    { 
     static void Main() 
     { 
      List list = new List(); 

      list.Append(3); 
      Console.WriteLine(list); 

      list.Append(1); 
      Console.WriteLine(list); 

      list.Append(6); 
      Console.WriteLine(list); 

      list.Prepend(4); 
      Console.WriteLine(list); 

      // continued… 

// Continued… 

     list.Prepend(5); 
     Console.WriteLine(list); 

     list.DeleteFirst(4); 
     Console.WriteLine(list); 

     list.Prepend(2); 
     Console.WriteLine(list); 

     Console.WriteLine("Head data = " + list.Head); 
     Console.WriteLine("Tail data = " + list.Tail); 

     list.Clear(); 
     Console.WriteLine(list); 

     Console.WriteLine("IsEmpty = " + list.IsEmpty); 
    } 
} 



using System; 

class List 
{ 
    ListEntry head; 
    ListEntry tail; 

    class ListEntry 
    { 
     // Put declaration of ListEntry here. Nesting of the classes is valid. In fact, class nesting is 
     // preferable if one class is only used within the context of another class. 
    } 

    public List() 
    { 
     head = null; 
     tail = null; 
    } 

    // Continued… 


public int Head 
{ 
    get{ return head.Data; } 
} 

public int Tail 
{ 
    get{ return tail.Data; } 
} 

public bool IsEmpty 
{ 
    get{ return(head == null); } 
} 

public override string ToString() 
{ 
    string tmp = ""; 

    ListEntry current = head; 
    if(current == null) 
    { 
     tmp = "Empty"; 
    } 
    while(current != null) 
    { 
     tmp += current + " "; 
     current = current.Next; 
    } 
    return(tmp); 
} 

public void Append(int i) 
{ 
    ListEntry tmp = new ListEntry(i); 

    tmp.Next = null; 

    if(head == null) 
    { 
     head = tmp; 
    } 
    else 
    { 
     tail.Next = tmp; 
    } 
    tail = tmp; 
} 

public void Prepend(int i) 
{ 
    ListEntry tmp = new ListEntry(i); 

    tmp.Next = head; 

    if(head == null) 
    { 
     tail = tmp; 
    } 
    head = tmp; 
} 

public void DeleteFirst(int i) 
{ 
    ListEntry current = head; 
    ListEntry previous = null; 

    while(current != null && current.Data != i) 
    { 
     previous = current; 
     current = current.Next; 
    } 
    if(current == null) 
    { 
     throw new ArgumentException("List entry not found"); 
    } 

    // Continued… 


// Continued… 

    if(current == head) 
    { 
     head = current.Next; 
    } 
    else 
    { 
     previous.Next = current.Next; 
    } 
    if(current == tail) 
    { 
     tail = previous; 
    } 
} 

還有其他的方法，如： 甲排序（）方法 甲使用FindFirst（）方法 甲FindNext中（）方法 一個的insertBefore（）方法 的InsertAfter（）方法

但現在t他基本的很好..

Answer 1

鏈接列表是一種數據結構，用於收集一系列對象。 「頭」是序列中的第一項。 「尾巴」是序列中的最後一個對象。鏈接列表（節點）中的每個項目都有一個名爲Next的屬性（以及如果它是雙向鏈接，則爲Previous），該屬性指向列表中的Next或Previous項目。這些下一個和上一個項目只是指向集合中的下一個或上一個項目，因此要遍歷它們，您必須按順序執行它們。

想象鏈中的鏈接等鏈接列表。要到達列表中的第5個項目，您首先從鏈中的第一個鏈接開始，然後遵循它，直到到達第五個項目。希望這有所幫助。

http://en.wikipedia.org/wiki/Linked_list

Answer 2

在C＃（通用）一個簡單的單向鏈表實現：

public class LinkedList<T> 
{ 
    private Node<T> head; 

    public void AddAtFront(T data) 
    { 
     this.head = new Node<T>(data, this.head); 
    } 

    public void AddAtBack(T data) 
    { 
     var node = new Node<T>(data); 
     var current = this.head; 

     if (current == null) 
     { 
      this.head = node; 
     } 
     else 
     { 
      while (current.Next != null) 
      { 
       current = current.Next; 
      } 

      current.Next = node; 
     } 
    } 

    public Node<T> Front 
    { 
     get 
     { 
      return this.head; 
     } 
    } 

    public Node<T> Back 
    { 
     get 
     { 
      var current = this.head; 

      if (current != null) 
      { 
       while (current.Next != null) 
       { 
        current = current.Next; 
       } 
      } 

      return current; 
     } 
    } 

    public Node<T> RemoveAtFront() 
    { 
     var node = this.head; 

     if (node != null) 
     { 
      this.head = node.Next; 
     } 

     return node; 
    } 

    public Node<T> RemoveAtBack() 
    { 
     var current = this.head; 

     if (current != null) 
     { 
      if (current.Next == null) 
      { 
       this.head = null; 
      } 
      else 
      { 
       Node<T> nextToLast = null; 

       while (current.Next != null) 
       { 
        nextToLast = current; 
        current = current.Next; 
       } 

       nextToLast.Next = null; 
      } 
     } 

     return current; 
    } 
} 

和

public class Node<T> 
{ 
    private readonly T data; 

    private Node<T> next; 

    public Node(T data) 
    { 
     this.data = data; 
    } 

    public Node(T data, Node<T> next) 
    { 
     this.data = data; 
     this.next = next; 
    } 

    public T Data 
    { 
     get 
     { 
      return this.data; 
     } 
    } 

    public Node<T> Next 
    { 
     get 
     { 
      return this.next; 
     } 

     set 
     { 
      this.next = value; 
     } 
    } 
}