python實(shí)現(xiàn)單鏈表的方法示例-創(chuàng)新互聯(lián)

前言

首先說(shuō)下線性表，線性表是一種最基本，最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，通俗點(diǎn)講就是一維的存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)。

線性表分為順序表和鏈接表：

• 順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，稱為線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映像；
• 鏈?zhǔn)奖硎局傅氖怯靡唤M任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。而他既可以是連續(xù)的也可以不連續(xù)，是通過(guò)一個(gè)與后繼結(jié)點(diǎn)的連接信息構(gòu)建起來(lái)的。

*順序表（這個(gè)不是本次重點(diǎn)，簡(jiǎn)單介紹一下）

順序表是用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，查找元素是很方便的，但是如果要向其中添加刪除元素就不那么簡(jiǎn)單了。因?yàn)樘砑觿h除元素要先找到那個(gè)位置，由于順序表內(nèi)部是通過(guò)地址的連續(xù)才使他成為一個(gè)表，當(dāng)刪掉元素時(shí)，要把后面的元素全部向前移，填補(bǔ)上空出來(lái)的地址空間；添加元素也是一樣，需要先把該位置后面的元素向后移去，才能在這塊地址上添加元素。

以C語(yǔ)言為例：順序表可以通過(guò)一個(gè)數(shù)組來(lái)表示，每創(chuàng)建一個(gè)數(shù)組就對(duì)應(yīng)給他分配一塊內(nèi)存。當(dāng)然除了靜態(tài)分配空間，還可以動(dòng)態(tài)擴(kuò)展。后續(xù)的操作要在這塊內(nèi)存上進(jìn)行，一般都需要移動(dòng)數(shù)組元素，復(fù)雜度會(huì)很高。

在python中，順序表還有兩種表示方式：

• 一體式結(jié)構(gòu)
• 分離式結(jié)構(gòu)

這里的一體和分離是指表中的元素集合，和為實(shí)現(xiàn)正確操作而需記錄的信息，這兩部分是在同一塊空間還是在旁邊的一塊新的空間中。

python中的tuple和list就是采用了順序表的實(shí)現(xiàn)技術(shù)，不過(guò)tuple是不可變的，不支持對(duì)內(nèi)部的操作。而list是一個(gè)元素個(gè)數(shù)可變的線性表，支持添加刪除等操作。list的思想其實(shí)是和C語(yǔ)言中一樣的，只是對(duì)其中的功能進(jìn)行了一些封裝，也就是list的那些屬性。

*鏈?zhǔn)奖?/strong>

鏈表，顧名思義，相鄰結(jié)點(diǎn)是通過(guò)鏈來(lái)連接的，那么什么是鏈呢。我們知道，C語(yǔ)言中有指針，指針通過(guò)地址來(lái)找到他的目標(biāo)。如此說(shuō)來(lái)，一個(gè)節(jié)點(diǎn)不僅僅有他的元素，還需要有一個(gè)他下一個(gè)元素的地址。

那么，這里需要指針和地址。python中的指針是什么呢？下面先把這個(gè)放一下，先去理解一下python里面變量標(biāo)識(shí)的實(shí)質(zhì)。

先看一下這個(gè)，為什么a和b的id是一樣的呢？那我再問(wèn)一個(gè)問(wèn)題：python中交換兩個(gè)變量的值時(shí)怎樣來(lái)實(shí)現(xiàn)的？

1 a = 10
2 b = 20
3 a,b = b,a