資料結構:單向連結清單系列1--引言

 基礎知識

介紹：連結清單與數組一樣，同屬于線性表的一個子集。不同之處在于連結清單元素并不需要存儲到一塊連續的記憶體空間；

連結清單中的元素通過指針來連結并維護各個節點之間的聯系，可使用連續的記憶體空間、亦可不使用連續的記憶體空間。

使用連結清單的原因：

1、數組類型長度是固定的，一旦申明不可以修改長度。在實際使用中我們必須事先知道元素數量的上限。

2、實際使用過程中配置設定的數組上限的記憶體空間，而事實不一定占用那麼多空間。

3、插入删除成本高，必須要進行位移。插入平均位移n/2個元素，删除移動(n-1)/2個元素。最理想的時間成本

    O(1)即被删除/插入元素後面沒有元素。

連結清單有點：

1、動态配置設定記憶體，即用即申請，占用空間大小也是動态的。

2、插入、删除友善，特别是在頭和尾，修改指針位址即可。

缺點：

1、不可以随機通路，必須周遊。二分查找時間複雜度為O(n),數組二分查找時間複雜度O(log2n) （注：O(n)> O(log2n)）

2、清單中每個節點還需要額外的記憶體空間存儲指針域（鍊）資料

3、數組中元素占用的存儲空間是連續的，可以根據索引進行通路元素,連結清單不支援此操作。

資料展現：

連結清單第一個節點叫頭節點。如果連結清單為空，資料域、指針域(鍊、引用)都是NULL

c語言中通常用結構展示資料，在java或者C#中用類和另外一個節點類(Node)來表示，LinkedList類包含Node類型的引用。

建立3個節點并周遊

c語言:

// A simple C program to introduce 
// a linked list 
#include <stdio.h>data); 
        n = n->next; 
    } 
} 

// Program to create a simple linked 
// list with 3 nodes 
int; 
  
    // Link second node with the third node 
    second->next =; 
}      

輸出結果：

1 2 3      

// A simple Java program to introduce a linked list 
public class; 
        } // Constructor 
) { 
            System.out.print(n.data + " "); 
            n =); 
        Node second = new Node(2); 
        Node third = new Node(3); 
  
        /* Three nodes have been allocated dynamically. 
          We have references to these three blocks as first,   
          second and third 
  
          llist.head        second              third 
             |                |                  | 
             |                |                  | 
         +----+------+     +----+------+     +----+------+ 
         | 1  | null |     | 2  | null |     |  3 | null | 
         +----+------+     +----+------+     +----+------+ */
        
        llist.printList(); 
    } 
}      

using; 
        } // Constructor 
) { 
            Console.Write(n.data + " "); 
            n =); 
        Node second = new Node(2); 
        Node third = new Node(3); 
  
        /* Three nodes have been allocated dynamically.  
        We have references to these three blocks as first,  
        second and third  
  
        llist.head     second             third  
            |             |                 |  
            |             |                 |  
        +----+------+     +----+------+     +----+------+  
        | 1  | null |     | 2  | null |     | 3  | null |  
        +----+------+     +----+------+     +----+------+ */
        
        llist.printList(); 
    } 
}