18.鏈表的提出

根據(jù)線性表的實際存儲方式，分為兩種實現(xiàn)模型：

順序表，將元素順序地存放在一塊連續(xù)的存儲區(qū)里，元素間的順序關系由它們的存儲順序自然表示。

鏈表，將元素存放在通過鏈接構造起來的一系列存儲塊中。

為什么需要鏈表

順序表的構建需要預先知道數(shù)據(jù)大小來申請連續(xù)的存儲空間，而在進行擴充時又需要進行數(shù)據(jù)的搬遷，所以使用起來并不是很靈活。鏈表結構可以充分利用計算機內存空間，實現(xiàn)靈活的內存動態(tài)管理。

鏈表的定義

鏈表（Linked list）是一種常見的基礎數(shù)據(jù)結構，是一種線性表，但是不像順序表一樣連續(xù)存儲數(shù)據(jù)，而是在每一個節(jié)點（數(shù)據(jù)存儲單元）里存放下一個節(jié)點的位置信息（即地址）。

19.單鏈表的ADT模型

單向鏈表

單向鏈表也叫單鏈表，是鏈表中最簡單的一種形式，它的每個節(jié)點包含兩個域，一個信息域（元素域）和一個鏈接域。這個鏈接指向鏈表中的下一個節(jié)點，而最后一個節(jié)點的鏈接域則指向一個空值。

表元素域elem用來存放具體的數(shù)據(jù)。

鏈接域next用來存放下一個節(jié)點的位置（python中的標識）

變量p指向鏈表的頭節(jié)點（首節(jié)點）的位置，從p出發(fā)能找到表中的任意節(jié)點。

單鏈表的操作

is_empty() 鏈表是否為空

length() 鏈表長度

travel() 遍歷整個鏈表

add(item) 鏈表頭部添加元素

append(item) 鏈表尾部添加元素

insert(pos,item) 指定位置添加元素

remove(item) 刪除節(jié)點

search(item) 查找節(jié)點是否存在

20.Python中變量標識的本質

a=10 b=20 a,b=b,a

?a指向10的地址，b指向20的地址

a,b=b,a先從右邊開始

a,b=20,10

?

21.單鏈表及結點的定義代碼

節(jié)點實現(xiàn)

class SingleNode(object):"""單鏈表的結點"""def __init__(self,item):# _item存放數(shù)據(jù)元素self.item = item# _next是下一個節(jié)點的標識self.next = None

單鏈表的實現(xiàn)

class SingleLinkList(object):"""單鏈表"""def __init__(self):self._head = None #私有屬性

22.單鏈表的判空、長度、遍歷與尾部添加結點的代碼實現(xiàn)

單鏈表的實現(xiàn)

class SingleLinkList(object):"""單鏈表"""def __init__(self):self._head = Nonedef is_empty(self):"""判斷鏈表是否為空"""return self._head == Nonedef length(self):"""鏈表長度"""# cur初始時指向頭節(jié)點cur = self._headcount = 0# 尾節(jié)點指向None，當未到達尾部時while cur != None:count += 1# 將cur后移一個節(jié)點cur = cur.nextreturn countdef travel(self):"""遍歷鏈表"""cur = self._headwhile cur != None:print cur.item,cur = cur.nextprint ""

def append(self, item):"""尾部添加節(jié)點"""node = Node(item)if self.is_empty():self._head = nodeelse:# 移到鏈表尾部cur = self._headwhile cur.next != None:cur = cur.next# 將尾節(jié)點指向nodecur.next = node# 將node指向頭節(jié)點_headnode.next = self._head

23.單鏈表尾部添加和在指定位置添加

def add(self, item):"""頭部添加節(jié)點"""node = Node(item)node.next = self._headself._head = node def insert(self, pos, item):"""在指定位置添加節(jié)點"""if pos <= 0:self.add(item)elif pos > (self.length()-1):self.append(item)else:node = Node(item)cur = self._headcount = 0# 移動到指定位置的前一個位置while count < (pos-1):count += 1cur = cur.nextnode.next = cur.nextcur.next = node

24.單鏈表查找和刪除元素

def search(self, item):"""查找節(jié)點是否存在"""if self.is_empty():return Falsecur = self._headif cur.item == item:return True while cur != None:cur = cur.nextif cur.item == item:return Truereturn False def remove(self,item):cur = self.__headpre=Nonewhile cur != None:if cur.elem == item:if cur == self.__head:self.__head = cur.nextelse:pre.next = cur.nextbreakelse:pre = curcur = cur.next

25.單鏈表與順序表的對比

鏈表失去了順序表隨機讀取的優(yōu)點，同時鏈表由于增加了結點的指針域，空間開銷比較大，但對存儲空間的使用要相對靈活。

操作鏈表順序表

訪問元素	O(n)	O(1)
在頭部插入/刪除	O(1)	O(n)
在尾部插入/刪除	O(n)	O(1)
在中間插入/刪除	O(n)	O(n)

注意雖然表面看起來復雜度都是 O(n)，但是鏈表和順序表在插入和刪除時進行的是完全不同的操作。鏈表的主要耗時操作是遍歷查找，刪除和插入操作本身的復雜度是O(1)。順序表查找很快，主要耗時的操作是拷貝覆蓋。因為除了目標元素在尾部的特殊情況，順序表進行插入和刪除時需要對操作點之后的所有元素進行前后移位操作，只能通過拷貝和覆蓋的方法進行。

總結

以上是生活随笔為你收集整理的Python数据结构与算法（第三天）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。