從數(shù)據(jù)的邏輯結(jié)構(gòu)來分，數(shù)據(jù)元素之間存在的關(guān)聯(lián)關(guān)系被稱為數(shù)據(jù)的邏輯結(jié)構(gòu)潮罪。歸納起來略步，應(yīng)用程序中的數(shù)據(jù)大致喲如下四種基本的邏輯結(jié)構(gòu)。

• 集合：數(shù)據(jù)元素之間只有“同屬于一個(gè)集合”的關(guān)系
• 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系
• 樹形結(jié)構(gòu)：數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系
• 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)關(guān)系
  對(duì)于數(shù)據(jù)不同的邏輯結(jié)構(gòu)倡怎，在底層通常有兩種物理存儲(chǔ)結(jié)構(gòu)。
• 順序存儲(chǔ)結(jié)構(gòu)
• 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

線性表的定義及邏輯結(jié)構(gòu)

線性表（LinearList）是由n(n>=0)個(gè)數(shù)據(jù)元素(節(jié)點(diǎn))a1,a2,a3,...,an組成的有限序列贱枣。

線性表中每個(gè)元素必須具有相同的結(jié)構(gòu)(即擁有相同的數(shù)據(jù)項(xiàng)).線性表是線性結(jié)構(gòu)中最常用而又最簡單的一種數(shù)據(jù)結(jié)構(gòu)监署。

線性表中每個(gè)數(shù)據(jù)元素其實(shí)可以包含若千個(gè)數(shù)據(jù)項(xiàng)，例如纽哥，使用ai來代表線性表中的第i個(gè)元素焦匈，其中ai元素可以包含若千個(gè)數(shù)據(jù)項(xiàng)。關(guān)干線性表還可以有如下定義昵仅。

• 線性表中包含的數(shù)據(jù)元素個(gè)數(shù)n被稱為表的長度，當(dāng)線性表的長度為0是該表也被稱為空表。
• 當(dāng)n>0時(shí)摔笤，表可以表示為(a1,a2,a3,...,an)

對(duì)于一個(gè)非空够滑，有限的線性表而言，它總具有如下特征吕世。

• 總存在唯一的“第一個(gè)”數(shù)據(jù)元素彰触。
• 總存在唯一的“最后一個(gè)”數(shù)據(jù)元素。
• 除第一個(gè)數(shù)據(jù)元素外命辖，集合中的每一個(gè)數(shù)據(jù)元素都只有一個(gè)前驅(qū)的數(shù)據(jù)元素况毅。
• 除了最后一個(gè)數(shù)據(jù)元素外，集合中的每個(gè)數(shù)據(jù)元素都只有一個(gè)后繼的數(shù)據(jù)元素尔艇。

線性表的基本操作

如果需要實(shí)現(xiàn)一個(gè)線性表尔许，程序首先需要確定該線性表的每個(gè)數(shù)據(jù)元素。接下來终娃，應(yīng)該為該線性表實(shí)現(xiàn)如下基本操作味廊。

• 初始化：通常是一個(gè)構(gòu)造器，用于創(chuàng)建一個(gè)空的線性表
• 返回線性表的長度：該方法用于返回線性表中的數(shù)據(jù)元素
• 獲取指定索引處的元素:根據(jù)索引返回線性表的數(shù)據(jù)元素
• 按值查找數(shù)據(jù)元素的位置：如果線性表中存在一個(gè)或多個(gè)與查找值相等的數(shù)據(jù)元素棠耕，那么該方法返回一個(gè)搜索到的值相等的數(shù)據(jù)元素的索引余佛，否則返回-1.
• 直接插入數(shù)據(jù)元素：向線性表的頭部插入一個(gè)數(shù)據(jù)元素，線性表長度+1窍荧；
• 向指定位置插入數(shù)據(jù)元素:向線性表的指定索引處插入一個(gè)數(shù)據(jù)元素辉巡，線性表長度+1.
• 直接刪除數(shù)據(jù)元素：刪除線性表頭部的數(shù)據(jù)元素，線性表長度-1.
• 刪除線性表中指定位置的數(shù)據(jù)元素：刪除線性表中指定索引處的數(shù)據(jù)元素蕊退，線性表長度-1.
• 判斷線性表是否為空：該方法判斷線性表是否為空郊楣，如果線性表為空，則返回true,否則返回false
• 清空線性表：將線性表清空

順序存儲(chǔ)結(jié)構(gòu)

線性表的順序存儲(chǔ)結(jié)構(gòu)是指用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表的元素咕痛。當(dāng)程序采用順序存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)線性表時(shí)痢甘，線性表中相鄰元素的兩個(gè)元素ai和ai+1對(duì)應(yīng)的存儲(chǔ)地址loc(ai)和loc(ai+1)也是相鄰的。

換句話說茉贡，順序結(jié)構(gòu)線性表中數(shù)據(jù)元素的物理關(guān)系和邏輯關(guān)系是一致的塞栅，線性表中數(shù)據(jù)元素的存儲(chǔ)地址可按如下公式計(jì)算。

loc(ai)=loc(a0)+i*b(0<i<n)

上面公式中b代表每個(gè)數(shù)據(jù)元素的存儲(chǔ)單元腔丧。從上面公式可以看出放椰，程序獲取線性表中每個(gè)元素的存儲(chǔ)起始地址的時(shí)間相同，讀取表中數(shù)據(jù)元素的時(shí)間也相同愉粤。而且順序表中每個(gè)元素都可隨機(jī)存取砾医，因此順序存儲(chǔ)的線性表時(shí)一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。

為了使用順序結(jié)構(gòu)實(shí)現(xiàn)線性表衣厘，程序通常會(huì)采用數(shù)組來保存線性表中的數(shù)據(jù)元素如蚜。

線性表的插入運(yùn)算是指表的第i(0<=i<n)個(gè)位置插入一個(gè)新的數(shù)據(jù)元素x,是長度為n的線性表：

a0,...,ai-1,ai,...,an-1

變成長度為n+1的線性表：

a0,...,ai-1,x,ai,...,an-1
向順序結(jié)構(gòu)的線性表插入元素压恒，如圖所示：

linear.PNG

這里有一個(gè)要考慮的問題。由于順序結(jié)構(gòu)線性表底層采用數(shù)組來存儲(chǔ)數(shù)據(jù)元素错邦，因此插入數(shù)據(jù)元素是必須保證不會(huì)超出底層屬豬的容量探赫。如果線性表中元素的個(gè)數(shù)超出了底層數(shù)據(jù)的長度，那么就必須為該線性表擴(kuò)充底層數(shù)據(jù)的長度撬呢。

線性表的刪除運(yùn)算是指將表的第i(0<=i<n)個(gè)位置的數(shù)據(jù)元素刪除伦吠，使長度為n的線性表：

a0,...,ai-1,ai,ai+1,...,an-1

變成長度為n-1的線性表：

a0,...,ai-1,ai+1,...,an-1

從順序結(jié)構(gòu)的線性表中刪除元素，如下圖：

linear2.PNG

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表（簡稱為鏈表）將采用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素魂拦。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表不會(huì)按線性的邏輯順序來保存數(shù)據(jù)元素毛仪，他需要在每個(gè)數(shù)據(jù)元素里保存一個(gè)引用下一個(gè)數(shù)據(jù)元素的引用（或者叫指針）。

由于不是必須按順序存儲(chǔ)芯勘，鏈表在插入箱靴，刪除數(shù)據(jù)元素時(shí)比順序線性表塊的多，當(dāng)時(shí)查找一個(gè)節(jié)點(diǎn)或者訪問特點(diǎn)節(jié)點(diǎn)編號(hào)的節(jié)點(diǎn)則比順序線性表慢得多借尿。

使用鏈表結(jié)構(gòu)可以克服順序線性表(基于數(shù)組)需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)刨晴，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)的內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理路翻。但是鏈表結(jié)構(gòu)失去了數(shù)組隨機(jī)存取的優(yōu)點(diǎn)狈癞，同時(shí)鏈表由于增加了節(jié)點(diǎn)的指針域，空間開銷比較大茂契。

對(duì)于鏈表存儲(chǔ)結(jié)構(gòu)的線性表而言蝶桶，它的每個(gè)節(jié)點(diǎn)都必須包含數(shù)據(jù)元素本身和一個(gè)或兩個(gè)用來引用上一個(gè)/下一個(gè)節(jié)點(diǎn)的引用。也就是說掉冶，有如下公式：

節(jié)點(diǎn)=數(shù)據(jù)元素+引用下一個(gè)節(jié)點(diǎn)的引用+引用上一個(gè)節(jié)點(diǎn)的引用

如下圖是雙向鏈表節(jié)點(diǎn)示意圖真竖，其中每個(gè)節(jié)點(diǎn)中的prev代表前一個(gè)節(jié)點(diǎn)的引用，只有雙向鏈表的節(jié)點(diǎn)才存在prev引用厌小。

enty.PNG

鏈表是多個(gè)相互引用的節(jié)點(diǎn)的集合恢共，這個(gè)鏈表總是從頭節(jié)點(diǎn)開始，然后依次向后指向每個(gè)節(jié)點(diǎn)璧亚。

空鏈表就是頭節(jié)點(diǎn)為null的鏈表

單鏈表上的基本運(yùn)算

單鏈表指定是每個(gè)節(jié)點(diǎn)保留一個(gè)引用讨韭，改引用指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，沒有引用指向頭節(jié)點(diǎn)癣蟋，尾節(jié)點(diǎn)的next引用為null.單鏈表示意圖如下：

one_linked.PNG

對(duì)于單鏈表透硝，系統(tǒng)建立單鏈表的過程就是不斷添加節(jié)點(diǎn)的過程。動(dòng)態(tài)添加單鏈表有以下兩種方式疯搅。

• 頭插法建表：該方法從一個(gè)空表開始濒生，不斷地創(chuàng)建新節(jié)點(diǎn)，將數(shù)據(jù)元素存入節(jié)點(diǎn)的data域中幔欧，然后不斷地以新節(jié)點(diǎn)為頭節(jié)點(diǎn)罪治，讓新節(jié)點(diǎn)指向原有的頭節(jié)點(diǎn)
• 尾插法建表：該方法是將新節(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上丽声，因此需要為鏈表定義一個(gè)引用變量來保存鏈表的最后一個(gè)節(jié)點(diǎn)。

頭插法建立鏈表雖然算法簡單规阀，但生成的鏈表中節(jié)點(diǎn)的次序和輸入的順序相反:若希望二者次序一致恒序，則應(yīng)該采用尾插法來建立鏈表。

對(duì)于單鏈表而言谁撼，常用的操作有：

1. 查找
2. 插入
3. 刪除

1.查找操作

單鏈表的查找操作可以分為以下兩種：

• 按序號(hào)查找第index個(gè)節(jié)點(diǎn):從header節(jié)點(diǎn)依次向下在單鏈表中查找第index個(gè)節(jié)點(diǎn)口算法為，設(shè)header為頭滋饲，current為當(dāng)前節(jié)點(diǎn)(初始時(shí)current從heade厉碟，開始)，0為頭節(jié)點(diǎn)序號(hào)屠缭，i為計(jì)數(shù)器箍鼓，則可使current依次下移尋找節(jié)點(diǎn)，并使i同時(shí)遞增記錄節(jié)點(diǎn)序號(hào)呵曹，直到返回指定節(jié)點(diǎn)款咖。

• 在鏈表中查找指定的element元素:查找是否有等于給定值element的節(jié)點(diǎn)。若有奄喂，則返回首次找到的其值為element的節(jié)點(diǎn)的索引;否則铐殃，返回-l。查找過程從開始節(jié)點(diǎn)出發(fā)跨新，順著鏈表逐個(gè)將節(jié)點(diǎn)的值和給定值element做比較富腊。

2.插入操作

插入操作時(shí)將值為element的新節(jié)點(diǎn)插入到鏈表的第index個(gè)節(jié)點(diǎn)的位置上。因此域帐，首先找到索引的index-1的節(jié)點(diǎn)赘被，然后生成一個(gè)數(shù)據(jù)域?yàn)閑lement的新節(jié)點(diǎn)newNode，并令idnex-1處節(jié)點(diǎn)的next引用新節(jié)點(diǎn)肖揣，新節(jié)點(diǎn)的next引用原來index處的節(jié)點(diǎn)民假。

向i索引處插入節(jié)點(diǎn)的示意圖。

insert_linked.PNG

3.刪除操作

刪除操作是將鏈表的第index個(gè)節(jié)點(diǎn)刪去龙优。因?yàn)樵趩捂湵碇醒蛞欤趇ndex個(gè)節(jié)點(diǎn)是有index-1處的節(jié)點(diǎn)引用的，因此刪除index處節(jié)點(diǎn)將先獲取index-1處節(jié)點(diǎn)陋率，然后index-1處節(jié)點(diǎn)的next引用到原index+1處的節(jié)點(diǎn)球化，并釋放index處節(jié)點(diǎn)即可。

delete_linked.PNG

循環(huán)鏈表

循環(huán)鏈表是一種首尾相接的鏈表瓦糟。將單鏈表的尾節(jié)點(diǎn)next指針改為引用單鏈表header節(jié)點(diǎn)筒愚，這個(gè)單鏈表就成了循環(huán)鏈表。

循環(huán)鏈表具有一個(gè)顯著特征：鏈表的任一個(gè)節(jié)點(diǎn)出發(fā)均可找到表中的其他所有節(jié)點(diǎn)菩浙，因此巢掺，循環(huán)鏈表可以被視為“無頭無尾”,如下圖：

recycler_linked.PNG

循環(huán)鏈表中的第一個(gè)節(jié)點(diǎn)之前就是最后一個(gè)節(jié)點(diǎn)句伶，反之亦然。循環(huán)鏈表的無邊界使得它實(shí)現(xiàn)了很多方法時(shí)會(huì)更容易陆淀，在這樣的鏈表上設(shè)計(jì)算法會(huì)比普通鏈表更加容易考余。

新加入的節(jié)點(diǎn)應(yīng)該是在第一個(gè)節(jié)點(diǎn)之前（采用頭插法插入），還是最后一個(gè)節(jié)點(diǎn)之后（采用尾插法插入）轧苫，可以根據(jù)實(shí)際要求靈活處理楚堤，具體的實(shí)現(xiàn)區(qū)別不大。

雙向鏈表

如果為每個(gè)節(jié)點(diǎn)保留兩個(gè)引用prev和next,讓prev指向當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)含懊，讓next指向當(dāng)前節(jié)點(diǎn)的下一頁節(jié)點(diǎn)身冬，此時(shí)的鏈表既可以向后依次訪問每個(gè)節(jié)點(diǎn)，也可以向前依次訪問節(jié)點(diǎn)岔乔，這種形式的鏈表被稱為雙向鏈表酥筝。示意圖如下：

double_linked.PNG

雙向鏈表是一種對(duì)稱結(jié)構(gòu)，它克服了單鏈表上指針單向性的缺點(diǎn)雏门，其中每個(gè)節(jié)點(diǎn)既可以向前引用嘿歌，也可以向后引用，這樣可以更方便地插入茁影、刪除數(shù)據(jù)元素宙帝。

與單鏈表類似的是，如果將鏈表的header節(jié)點(diǎn)與tail節(jié)點(diǎn)鏈在一起就構(gòu)成了雙向循環(huán)鏈表呼胚。

雙向鏈表的查找

由于雙向鏈表既可以從header節(jié)點(diǎn)開始依次向后搜索每個(gè)節(jié)點(diǎn)茄唐，也可以從tail節(jié)點(diǎn)開始依次向前搜索每個(gè)節(jié)點(diǎn)，因此當(dāng)程序試圖從雙向鏈表中搜索指定索引處的節(jié)點(diǎn)時(shí)蝇更，既可以從該鏈表的header節(jié)點(diǎn)開始搜索沪编，也可以從該鏈表的tail節(jié)點(diǎn)開始搜索。至于到底應(yīng)該從header開
始搜索年扩，還是應(yīng)該從tail開始搜索蚁廓，則取決于被搜索節(jié)點(diǎn)是更靠近header，還是更靠近tail.

一般來說厨幻，可以通過被搜索index的值來判斷它更靠近header還是更靠近tail.如果index<size/2相嵌，則可判斷該位置更靠近header，應(yīng)從header開始搜索;反之况脆，則可判斷該位置更靠近tail饭宾，那就應(yīng)從tail開始搜索口

雙向鏈表的插入

雙向鏈表的插入操作更復(fù)雜，向雙向鏈表中插入一個(gè)新節(jié)點(diǎn)必須同時(shí)修改兩個(gè)方向的指針（即引用）格了。如下圖所示：

insert_double_linked.PNG

雙向鏈表的刪除

在雙向鏈表中看铆，刪除一個(gè)節(jié)點(diǎn)需要同時(shí)修改兩個(gè)方向的指針，雙向鏈表中刪除節(jié)點(diǎn)的操作盛末，如下圖所示：

delete_double_linked.PNG

線性表的分析

線性表的順序的順序和鏈?zhǔn)絻煞N實(shí)現(xiàn)各有優(yōu)勢(shì)：如下

線性表的功能

線性的本質(zhì)上是一個(gè)充當(dāng)容器的工具類报咳，當(dāng)程序有一組結(jié)構(gòu)相同的數(shù)據(jù)元素需要保存時(shí)侠讯，就可以考慮使用線性表來保存它們。

從某種程度來說暑刃，線性表是數(shù)組的加強(qiáng)，線性表比數(shù)據(jù)多了如下幾個(gè)功能：

• 線性表的長度可以動(dòng)態(tài)改變膜眠，而java數(shù)組的長度是固定的
  -線性表可以插入元素岩臣，而數(shù)組無法插入元素
• 線性表可以刪除元素，而數(shù)組無法刪除元素宵膨，數(shù)組只能將指定元素賦為null,但各種元素依然存在
• 線性表提供方法來搜索指定元素的位置架谎，而數(shù)組一般不提供該方法
• 線性表提供方法來清空所有元素的位置，而數(shù)組一般不提供該方法

從上面線性表的實(shí)現(xiàn)能發(fā)瓏線性表比數(shù)組功能強(qiáng)大的理由是辟躏，順序結(jié)構(gòu)的線性表可以說是包裝過的數(shù)組谷扣，自然會(huì)提供更多額外的方法來簡化操作。

對(duì)于大部分,Java程序員來說捎琐，其實(shí)經(jīng)常在使用線性表List. Java的List接口就代表了線性表会涎，線性表的兩種實(shí)現(xiàn)分別是ArrayList和LinkedList其中LinkedList還是一個(gè)雙向鏈表。JDK提供的線性表有如下圖：

listtype.PNG