鏈表是一種數據結構還是數據類型？

01-03

學習數據結構和演算法，對數組、鏈表、棧、隊列、樹這幾個概念之間的邏輯關係有點疑問。
我的理解是，數組和鏈表是兩種數據存儲方式，連續存儲和非連續存儲。而棧、隊列、樹這些是數據類型，每一種都可以採用數組來實現或者鏈表來實現。也就是說，這是兩個不同維度的概念。如果把數據類型定義為可以施加一組特定操作的數據元素的集合，那麼數據結構就是數據元素的存儲方式（連續/非連續），而演算法就是每個操作的具體實現，數據類型=數據結構+演算法。
但是為什麼數據結構的教材總是把鏈表與棧、隊列放在一起，感覺他們並不是一個維度上的概念。不知道我的理解是否正確。
————————————————————————————
補充（2/5，21:38）：

謝謝大家的回答，目前看來大家還沒有一個統一的認識。
我又重新看了兩本書
Data Structures and Algorithm Analysis in C, 2nd Edition
Algorithms, 4th Edition
雖然有不同的說法，但是一個自洽的看法是：

List, Stack, Queue等是Abstract Data Type（或者說是Data Type？演算法第四版交換使用ADT和Data Type這兩個詞，似乎不作區分）

而Array和Linked List是Data Structure，側重的是數據的存儲方式。

每一種ADT都既可以用Array來實現，也可以用Linked List來實現。

有答主說Array和Linked List都是Data Type，比如@Belleve 的回答。我能理解這種觀點，但是如果採取這種觀點，那麼Array應該也有非連續存儲的實現方式，Linked List也有連續存儲的實現方式，有沒有這種實現方式的例子呢？另外，如果把Array和Linked List看做數據類型，那麼「Queue可以用Array或者Linked List來實現」這句話就顯得很奇怪，這句話想表達的是Queue可以用連續存儲也可以非連續存儲，但是卻把Array等同於連續存儲，Linked List等同於非連續存儲。
有點鑽牛角尖和摳字眼，但是作為初學者，概念之間的邏輯關係混亂實在很頭痛，望大家指導。

哈哈這個鏈表的問題真算是知乎的月經問題啦。我覺得大家與其多想，不如多查。畢竟Google和維基什麼都知道。

數據類型：In computer science and computer programming, a data type or simply type is a classification of data which tells the compiler or interpreter how the programmer intends to use the data.

數據類型裡面常用的就是實數整數數組什麼的，這些比較好理解。另外的就是抽象數據結構：堆/棧（此處非虛擬內存的堆棧），樹，有序/無序集合，優先隊列，等等等等。這些東西相比起普通數據類型確實比較「抽象」，所以需要專門開一門課告訴你有哪些比較常用。

數據結構：In computer science, a data structure is a particular way of organizing data in a computer so that it can be used efficiently.

然後就是具體數據結構實現：就是你經常寫的什麼splay tree，treap（實現有序集合），Fibonacci Heap（實現優先隊列），hash table（實現無序集合），union-find（實現聯通森林）等等。

那麼鏈表是用來實現堆、棧和一些其它比較簡單的數據結構用的，所以自然是一個數據結構。

In computer science, a linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence.

當然了，其實這些問題雖然並不難但是確實很多人都搞不太清楚，我們投非理論的會議，因為審稿人搞不清data type和data structure於是得到很多莫名其妙匪夷所思的comments是很常見的，我們也比較頭大且沒什麼辦法……更有甚者連data structure和application都分不太清……比如paper是實現一個data type然後reviewer說在某個application裡面不用某個query啊，等等……

ps. @王贇 Maigo 其實恰恰相反在演算法和數據結構中會大量提到數據類型，比如我提出了一種新的BST，我一般paper的abstract會粗略用一兩句話說他支持哪些ADT，這樣我就不用說我這個數據結構能幹啥了（當然這個例子有點low，正常人都知道search tree能幹嘛）。而我一篇演算法論文，演算法描述中會說我需要一個priority queue，那麼具體用什麼實現取決於input和場景，而一般不會在演算法中說我需要一個binomial heap。具體的數據結構只會出現在分析複雜度中，而替換這個數據結構並不影響演算法本身的正確性，所以因為其不必要性，不會出現在演算法描述中。因此數據類型是個很好的在演算法和數據結構之間的橋樑。

我的體會是，「數據類型」指的是整型、實型、字元型、類這樣的東西，是在討論編程語言的時候使用的概念，在演算法和數據結構的語境中基本不提。

而數組、鏈表、棧、隊列這些都是「數據結構」。正如你所說，這些數據結構之間還存在不同的關注點和層次關係：數組、鏈表注重數據間的排列方式，棧、隊列注重操作；後者可以用前者實現。所以我覺得可以把「數組、鏈表」等稱為「數據的物理結構」；「棧、隊列」等稱為「數據的邏輯結構」。

有些數據結構既可以是物理結構又可以是邏輯結構，比如樹 —— 一般邏輯上「樹」的概念，在物理上也是用樹形結構（結構體 + 指針）實現的。但也有特殊情況，比如邏輯上的「堆」在物理上可以用數組實現；邏輯上的「並查集」在物理上可以用「森林」來實現。

混了，這兩個概念並不衝突，數據結構是數據的組織形式和具體實現，而數據類型是指類型系統，是為了保證程序不出錯而將計算結果進行標記的系統，不是你們現在需要研究的內容

數組和鏈表當然是類型，兩者側重點差得遠了

數組更接近一個索引到元素類型的映射

鏈表則是側重「下一項」（單鏈表）/「前後項」（雙鏈表）

data List : Type -&> Type where Nil : List a Cons : a -&> List a -&> List a

Array : Type -&> Type Array a = (n : Nat) ** (Morphism (Range 0 n) a)

至於具體的存儲形式那是另一回事了

是數據結構，不是數據類型。數組、鏈表、棧、隊列、樹，你說的每一個都是數據結構，它們強調的是數據在內存（或外存）中如何組織、如何被演算法使用這件事。數據結構也可以有不同層次，比如說數組、鏈表更注重於存放方式，棧、隊列更注重於對外介面，它們可能是同一個東西的不同層次的抽象。樹在這裡稍微特殊一些，它有的時候指樹狀結構，這是一種數據結構；有的時候指數學上的樹，它包括了一些元素和元素之間的、有約束的關係，更接近於數據類型一些。

數據類型則指的是數據的內容，而跟組織方式無關。它要求數據的內容符合某些約束條件，比如說：

三個有序的元素

不定長的元素序列

不定大小的元素集合

也可能規定的非常詳細：

第一個元素是32個二進位位表示的整數，第二個元素是剛好10個字元的字元串，第三個元素是一個二進位位的有序三元組

也可能是抽象、泛型的：

包含全部為某種類型T的元素的長度為5的序列

屬於某個數據類型的數據可能按照需要用各種各樣的方式來表示，而不影響數據的內容，比如說在內存中可能表示為數組，可能表示為鏈表，還可能表示為JSON字元串、XML等等。如果數據內容符合這個約束條件，那麼它就可能用相同的一種或幾種數據結構來表示，但數據內容本身是跟數據結構無關的。

數據結構。你可說鏈表的節點是一個自定義數據類型，但鏈表是數據結構

數據結構好理解，就是數據的組織形式和訪問方式。數組，鏈表（包括單向鏈表，雙向鏈表，循環鏈表，雙向循環鏈表），棧、隊列、樹。

數據類型的含義要取決於上下文。如果是程序設計語言的上下文，就是提供給程序員使用的數據的種類（變數，字面量，操作），有基本數據類型（位元組，整型，浮點數），也有複合數據類型，如數組，字元串，映射，也有自定義數據類型如結構體。在面向對象程序設計語言中，一個類也可以作為數據類型，所以鏈表，集合，樹都可以是一種數據類型。

看題主的描述，題主所說的"數據類型"應該是特指ADT吧。

先複習一下概念：

數據結構：是相互之間存在一種或多種特定關係的數據元素的集合，包括邏輯結構和物理結構。
數據類型：是一個值的集合和定義在這個值集上的一組操作的總稱。
抽象數據類型：是指一個數學模型以及定義在該模型上的一組操作。

先說結論，鏈表是數據結構。鏈表實際上可以認為是一種數據的物理組織形式,是用指針或對象的引用組織起的一種數據的存儲方式.

至於題主的疑惑「為什麼鏈表總是和棧，隊列...等放在一起」

@吳聰

的回答里也說了「一般將鏈表和棧之類的放在一起講是因為早期的編程語言沒有內置鏈表
」

比如C要利用結構體和指針來實現鏈表

struct node{ int value; struct node *next; };

以及自己實現一系列的操作（創建，插入，刪除，遍歷....）讓人產生了一種鏈表是ADT的錯覺，實際上這些操作早就在定義在真正的ADT，線性表上了。

毫無疑問，鏈表是實現各種ADT的一種重要的數據結構，線性表，樹等都依賴鏈表的實現。

我真的看不下去這個問題了。

我先問題主一道題，下列數據結構中,_______ 是線性結構.

A．哈希表 B.二叉樹 C.有向圖 D.串

然後我回答你的問題，List, Stack, Queue可以並列，它們都是線性表，後兩者是特殊的線性表。數據結構=邏輯結構+物理結構，線性表是邏輯結構的概念。物理結構則分為順序、鏈式、散列、索引，前兩者是線性的，後兩者是非線性。所以你應該知道ArrayList和LinkedList為什麼要這樣分了吧？List指它邏輯上的結構，Array和Linked指物理上的。

數組(其實應該說順序表)和鏈表是什麼？都是List，都是邏輯上的線性表，只不過物理結構不同。你要是還不理解呢，你往後讀，樹圖都可以存儲在數組裡，所以數組在邏輯上一定是線性表嗎？不，還可能是二叉樹等等。還有像鄰接表、鄰接矩陣這種數據結構，也有自己的邏輯結構和物理結構。

數據類型則是一個大的概念，子概念還有原子數據類型、結構數據類型、抽象數據類型等等。原子數據類型就像int,float這種，抽象數據類型則是一種數學模型，可以用高級編程語言里的基本數據類型來實現。你可以認為它是數據結構邏輯上的部分。

Array、ArrayList、LinkedList都是數據類型，你可以思考一下它們的聯繫和區別。

總之，數據結構和數據類型並不是嚴格對立的。

原答案：

根據題目描述我覺得題主還是應該再讀一遍書……

_(:_」∠)_分割線_(:_」∠)_

評論答題主：

回復 Euclid ：「數據結構」和「數據類型」兩個概念的本質是什麼，區別與聯繫是什麼？ - 牛肉絲的回答 - 知乎 http://www.zhihu.com/question/21165020/answer/118852959

可以看看這個答案。由於國內大部分教材用的都是嚴書，所以這裡只根據嚴書內容解釋，你可以認為數據結構是指相互之間存在著一種或多種關係的數據元素的集合和該集合中數據元素之間的關係組成。數據結構又可以分為物理結構和邏輯結構。物理結構就是指數據結構在計算機中的存儲，通常有兩種不同的表示方法，順序和鏈式，對應數組和鏈表。邏輯結構有集合、線性表、樹圖等，棧和隊列都是線性表。至於數據類型、抽象數據類型、數據結構的解釋可以看看開頭那個鏈接。這些解釋都是課本上的死東西，難免有不足的地方，但還是易於入門者理解的。

你可以把內存整個看成一個巨大的數組，於是任何東西都可以用數組實現。但是這並不表示數組就不是「數據結構」了。任何數據的組織形式都是數據結構，用簡單的結構實現複雜的結構不是很常見嗎。將來棧、隊列這些東西也可以用來實現更複雜的東西，你不能因此就開除他們的結構籍。

我認為數據類型具有原子性，而數據結構可向下分割。整型、浮點型的位具有權重。而點陣圖字元串的基本元素互相之間沒有依賴關係。

有一點可以攻詰：

tree是一個array嗎？

不是，如果用array實現tree的話會失去刪除和插入的優勢。

tree是一個linked list嗎？

不是，linked list不是必須結構，node只需要有child ptr就可以了。

tree是用不連續存儲實現的嗎？

是的。

linked list代表了不連續存儲？

。。。

所以tree就是tree，它至少在軟體層面上不屬於linked list或者array的上級。同理其他數據結構也都有自己的特點不一定要建在array或list上。

再舉一個栗子，hash table。同理既不是array也不是linked list。

queue和stack倒是可以用linked list和array來寫，那是因為他們結構如此。

array不太可能是不連續存儲，因為它性質如此。linked list可以是連續存儲的，只是在應用的時候它存儲在連續空間里的性質不怎麼重要。

至於queue可以用array也可以用linked list來實現，這句話的意思是我們既不需要O(1)的插入和刪除中間node，也不需要O(logN)的搜索，只要能知道頭尾和update頭尾就可以了。

鏈表是一種存儲結構，是指物理層次上數據存儲的一種方式。

線性表什麼的是邏輯結構，是指數據本身所具有的一種關係。

邏輯結構+存儲結構＝數據結構。

所以說邏輯結構中的鏈表是數據結構邏輯上不對。

至於類型更不可能了。adt除了存儲結構還要有相應操作。比如int的具體操作，加減乘除取余位運算

adt＝存儲結構+操作

來看看演算法第四版對鏈表的定義：

是數據結構不是數據類型數據類型主要關心存儲怎樣的數據怎樣訪問它數據結構主要關心數據在內存中的組織形式

錯了請指正。

我覺得是數據結構。

我覺得既是數據結構，又是數據類型。

在使用的時候，關注的是鏈表及定義在鏈表上的操作，是抽象好的，就跟使用內置類型差不多，表現為數據類型。

在定義的時候，關注的是內部實現，具體的存儲安排等等，關注的是結構。

數組和鏈表是基礎的數據結構

代表兩種數據存儲方式：連續的和離散的

隊列棧等數據結構都是在這基礎上的封裝

個人認為數據類型是指數據是屬於哪一類的，其具體指的是數據。而數據結構是指由數據組成的結構，或者說儲存數據所用的結構。

所以我覺得鏈表是儲存數據所用的一種結構，應該屬於數據結構

題主的理解是對的。鏈表不應該和堆棧與隊列並列，不是一個維度上的概念。