Python線性表種的單鏈表怎么實(shí)現(xiàn)

這篇文章主要介紹“Python線性表種的單鏈表怎么實(shí)現(xiàn)”的相關(guān)知識，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“Python線性表種的單鏈表怎么實(shí)現(xiàn)”文章能幫助大家解決問題。

1. 線性表簡介

線性表是一種線性結(jié)構(gòu)，它是由零個或多個數(shù)據(jù)元素構(gòu)成的有限序列。線性表的特征是在一個序列中，除了頭尾元素，每個元素都有且只有一個直接前驅(qū)，有且只有一個直接后繼，而序列頭元素沒有直接前驅(qū)，序列尾元素沒有直接后繼。

數(shù)據(jù)結(jié)構(gòu)中常見的線性結(jié)構(gòu)有數(shù)組、單鏈表、雙鏈表、循環(huán)鏈表等。線性表中的元素為某種相同的抽象數(shù)據(jù)類型。可以是C語言的內(nèi)置類型或結(jié)構(gòu)體，也可以是C++自定義類型。

2. 數(shù)組

數(shù)組在實(shí)際的物理內(nèi)存上也是連續(xù)存儲的，數(shù)組有上界和下界。C語言中定義一個數(shù)組：

數(shù)組下標(biāo)是從0開始的，a[0]對應(yīng)第一個元素。其中，a[0]稱為數(shù)組a的下界，a[6]稱為數(shù)組a的上屆。超過這個范圍的下標(biāo)使用數(shù)組，將造成數(shù)組越界錯誤。

數(shù)組的特點(diǎn)是：數(shù)據(jù)連續(xù)，支持快速隨機(jī)訪問。

數(shù)組分為固定數(shù)組與動態(tài)數(shù)組。其中固定數(shù)組的大小必須在編譯時就能夠確認(rèn)，動態(tài)數(shù)組允許在運(yùn)行時申請數(shù)組內(nèi)存。復(fù)雜點(diǎn)的數(shù)組是多維數(shù)組，多維數(shù)組實(shí)際上也是通過一維數(shù)組來實(shí)現(xiàn)的。在C語言中，可以通過malloc來分配動態(tài)數(shù)組，C++使用new。另外，C++的標(biāo)準(zhǔn)模板庫提供了動態(tài)數(shù)組類型vector以及內(nèi)置有固定數(shù)組類型array。

Python中l(wèi)ist可以被認(rèn)為是封裝好的數(shù)組。

3. 單向鏈表

單向鏈表是鏈表的一種。鏈表由節(jié)點(diǎn)所構(gòu)成，節(jié)點(diǎn)內(nèi)含一個指向下一個節(jié)點(diǎn)的指針，節(jié)點(diǎn)依次鏈接成為鏈表。因此，鏈表這種數(shù)據(jù)結(jié)構(gòu)通常在物理內(nèi)存上是不連續(xù)的。鏈表的通常含有一個頭節(jié)點(diǎn)，頭節(jié)點(diǎn)不存放實(shí)際的值，它含有一個指針，指向存放元素的第一個節(jié)點(diǎn)。

class Node():
"""
單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個屬性：val 和 next。
val 是當(dāng)前節(jié)點(diǎn)的值，
next 是指向下一個節(jié)點(diǎn)的指針/引用。
"""
def __init__(self, value):
# 存放元素數(shù)據(jù)
self.val = value
# next是下一個節(jié)點(diǎn)的標(biāo)識
self.next = None

設(shè)計鏈表的實(shí)現(xiàn)

您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個屬性：val 和 next。val 是當(dāng)前節(jié)點(diǎn)的值，next 是指向下一個節(jié)點(diǎn)的指針/引用。如果要使用雙向鏈表，則還需要一個屬性 prev 以指示鏈表中的上一個節(jié)點(diǎn)。假設(shè)鏈表中的所有節(jié)點(diǎn)都是 0-index 的。

在鏈表類中實(shí)現(xiàn)這些功能：

• get(index)：獲取鏈表中第 index 個節(jié)點(diǎn)的值。如果索引無效，則返回-1。

• addAtHead(val)：在鏈表的第一個元素之前添加一個值為 val 的節(jié)點(diǎn)。插入后，新節(jié)點(diǎn)將成為鏈表的第一個節(jié)點(diǎn)。

• addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個元素。

• addAtIndex(index,val)：在鏈表中的第 index 個節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)。如果 index 等于鏈表的長度，則該節(jié)點(diǎn)將附加到鏈表的末尾。如果 index 大于鏈表長度，則不會插入節(jié)點(diǎn)。

• deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個節(jié)點(diǎn)。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Author : Young
@File : linked_list2.py
@version : 1.0
@Time : 2019/4/5 11:06
Description about this file:

"""
class Node():
"""
單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個屬性：val 和 next。
val 是當(dāng)前節(jié)點(diǎn)的值，
next 是指向下一個節(jié)點(diǎn)的指針/引用。
"""

def __init__(self, value):
# 存放元素數(shù)據(jù)
self.val = value
# next是下一個節(jié)點(diǎn)的標(biāo)識
self.next = None


class SingleLinkList():
def __init__(self, node=None):
# 頭節(jié)點(diǎn)定義為私有變量
self._head = node

def is_empty(self):
# 判斷鏈表是否為空
if self._head is None:
return True
else:
return False

def get(self, index: int) -> int:
"""
獲取鏈表中第 index 個節(jié)點(diǎn)的值。如果索引無效，則返回-1
:param index: 索引值
:return:
"""
if self._head is None:
return -1
cur = self._head
for i in range(index):
if cur.next is None:
return -1
cur = cur.next
return cur.val

def length(self):
"""
cur游標(biāo)，用來移動遍歷節(jié)點(diǎn)
count用來計數(shù)
:return: 返回鏈表的長度
"""
cur = self._head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count

def travel(self):
"""
遍歷整個鏈表
:return:
"""
cur = self._head
while cur is not None:
print(cur.elem, end=' ')
cur = cur.next

def add_at_head(self, val: int) -> None:
"""
在頭部添加一個節(jié)點(diǎn)
:param val:
:return: None
"""
# 先創(chuàng)建一個保存item值的節(jié)點(diǎn)
node = Node(val)
# 判斷鏈表是否為空
if self._head is None:
self._head = node
else:
# 將新節(jié)點(diǎn)的鏈接域next指向頭節(jié)點(diǎn)，即_head指向的位置
node.next = self._head
# 將鏈表的頭_head指向新節(jié)點(diǎn)
self._head = node

def add_at_tail(self, val: int) -> None or int:
"""
在尾部添加一個節(jié)點(diǎn)
:param item:
:return:
"""
node = Node(val)
# 若鏈表為空，直接將該節(jié)點(diǎn)作為鏈表的第一個元素
if self._head is None:
self._head = node
else:
cur = self._head
while cur.next is not None:
cur = cur.next
cur.next = node

def add_at_index(self, index: int, val: int) -> None:
"""
在指定位置pos添加節(jié)點(diǎn)
pos從0開始
:param index:
:param val:
:return:
"""
# 若指定位置pos為第一個元素之前，則執(zhí)行頭部插入
if index <= 0:
self.add_at_head(val)
# 若指定位置超過鏈表尾部，則執(zhí)行尾部插入
elif index >= self.length():
self.add_at_tail(val)
# 找到指定位置
else:
# pre用來指向指定位置pos的前一個位置pos-1，初始從頭節(jié)點(diǎn)開始移動到指定位置
pre = self._head
count = 0
node = Node(val)
# 在目標(biāo)節(jié)點(diǎn)的前一位停下
while count < (index - 1):
count += 1
pre = pre.next
# 先將新節(jié)點(diǎn)node的next指向插入位置的節(jié)點(diǎn)
node.next = pre.next
# 將插入位置的前一個節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
pre.next = node

def delete_at_index(self, index: int) -> None or int:
"""
如果索引 index 有效，則刪除鏈表中的第 index 個節(jié)點(diǎn)。
:param index: 對應(yīng)的索引值
:return: -1表示為異常
"""
pre = None
cur = self._head
if index is 0:
self._head = None
for i in range(index):
if cur.next is None:
# raise IndexError("越界")
return -1
pre = cur
cur = pre.next
else:
pre.next = cur.next

def search(self, val: int) -> True or False:
"""
查找節(jié)點(diǎn)是否存在
:param val: 節(jié)點(diǎn)的val值
:return:
"""
cur = self._head
while cur is not None:
if cur.val == val:
return True
else:
cur = cur.next
return False

if __name__ == '__main__':
obj = SingleLinkList()
obj.add_at_head(1)
obj.add_at_tail(3)
obj.add_at_index(1, 2)
obj.travel()
obj.delete_at_index(1)
obj.travel()

鏈表與順序表的對比

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

鏈表與順序表的各種操作復(fù)雜度如下所示：

關(guān)于“Python線性表種的單鏈表怎么實(shí)現(xiàn)”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點(diǎn)。