冰凍非一日之寒

線性表是n個數(shù)據(jù)元素的有限序列。

線性表是一種真正的動態(tài)數(shù)據(jù)結(jié)構，不需要處理固定容量問題，長度可根據(jù)需要增長或縮短，即需要存儲多少個數(shù)據(jù)，就開辟多少個存儲單元。

前面講到的動態(tài)數(shù)組、棧、隊列三種數(shù)據(jù)結(jié)構，底層實現(xiàn)都是依托靜態(tài)數(shù)組，靠resize()方法解決固定容量問題。

線性表也是最簡單的動態(tài)數(shù)據(jù)結(jié)構，后面會講到二分搜索數(shù)、AVL樹、紅黑樹等更加復雜的動態(tài)數(shù)據(jù)結(jié)構，其原理也是建立在線性表這種數(shù)據(jù)結(jié)構基礎上的

特點：

存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素；

存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素；

除第一個元素外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)；

除最后一個元素外，集合中的每個數(shù)據(jù)元素均只有一個后繼。

線性表的順序表示指的是用一組連續(xù)的存儲單元依次存儲實現(xiàn)線性表的數(shù)據(jù)元素。

線性表的鏈式表示指的是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這個存儲單元可以是連續(xù)的，也可以是不連續(xù)的。

線性表的順序存儲結(jié)構的特點是邏輯關系上相鄰的兩個元素在物理位置上也相鄰，因此可以隨機存取表中任一元素。但是，這個特點也導致了這種存儲結(jié)構的弱點：在作插入或刪除操作時，需移動大量元素。而鏈式存儲結(jié)構，它不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構所具有的弱點，但同時也失去了順序表可隨機存取的優(yōu)點。

本章節(jié)，重點介紹線性表的鏈式存儲，簡稱鏈表。