冰凍非一日之寒
線性表是n個(gè)數(shù)據(jù)元素的有限序列。
線性表是一種真正的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，不需要處理固定容量問(wèn)題，長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短，即需要存儲(chǔ)多少個(gè)數(shù)據(jù)，就開辟多少個(gè)存儲(chǔ)單元。
前面講到的動(dòng)態(tài)數(shù)組、棧、隊(duì)列三種數(shù)據(jù)結(jié)構(gòu)，底層實(shí)現(xiàn)都是依托靜態(tài)數(shù)組，靠resize()方法解決固定容量問(wèn)題。
線性表也是最簡(jiǎn)單的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，后面會(huì)講到二分搜索數(shù)、AVL樹、紅黑樹等更加復(fù)雜的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，其原理也是建立在線性表這種數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上的
特點(diǎn)：
存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素；
存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素；
除第一個(gè)元素外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；
除最后一個(gè)元素外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。
線性表的順序表示指的是用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)實(shí)現(xiàn)線性表的數(shù)據(jù)元素。
線性表的鏈?zhǔn)奖硎?/b>指的是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這個(gè)存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。
線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰，因此可以隨機(jī)存取表中任一元素。但是，這個(gè)特點(diǎn)也導(dǎo)致了這種存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)：在作插入或刪除操作時(shí)，需移動(dòng)大量元素。而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒(méi)有順序存儲(chǔ)結(jié)構(gòu)所具有的弱點(diǎn)，但同時(shí)也失去了順序表可隨機(jī)存取的優(yōu)點(diǎn)。
本章節(jié)，重點(diǎn)介紹線性表的鏈?zhǔn)酱鎯?chǔ)，簡(jiǎn)稱鏈表。
