python資料結構連結串列之單向連結串列(例項講解)

python資料結構連結串列之單向連結串列(例項講解)
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

單向連結串列

單向連結串列也叫單連結串列,是連結串列中最簡單的一種形式,它的每個節點包含兩個域,一個資訊域(元素域)和一個連結域。這個連結指向連結串列中的下一個節點,而最後一個節點的連結域則指向一個空值。

表元素域elem用來存放具體的資料。

連結域next用來存放下一個節點的位置(python中的標識)

變數p指向連結串列的頭節點(首節點)的位置,從p出發能找到表中的任意節點。

節點實現


class Node(object):
"""單連結串列的結點"""
def __init__(self,item):
# item存放資料元素
self.item = item
# next是下一個節點的標識
self.next = None

單連結串列的操作

is_empty() 連結串列是否為空

length() 連結串列長度

travel() 遍歷整個連結串列

add(item) 連結串列頭部新增元素

append(item) 連結串列尾部新增元素

insert(pos, item) 指定位置新增元素

remove(item) 刪除節點

search(item) 查詢節點是否存在

單連結串列的實現


class Singlepnkpst(object):
"""單連結串列"""
def __init__(self):
self.__head = None
def is_empty(self):
"""判斷連結串列是否為空"""
return self.__head == None
def length(self):
"""連結串列長度"""
# cur初始時指向頭節點
cur = self.__head
count = 0
# 尾節點指向None,當未到達尾部時
while cur != None:
count  = 1
# 將cur後移一個節點
cur = cur.next
return count
def travel(self):
"""遍歷連結串列"""
cur = self.__head
while cur != None:
print(cur.item,end = ' ')
cur = cur.next
print("")

頭部新增元素


def add(self, item):
  """頭部新增元素"""
  # 先建立一個儲存item值的節點
  node = Node(item)
  # 將新節點的連結域next指向頭節點,即_head指向的位置
  node.next = self.__head
  # 將連結串列的頭_head指向新節點
  self.__head = nod

尾部新增元素


def append(self, item):
  """尾部新增元素"""
  node = Node(item)
  # 先判斷連結串列是否為空,若是空連結串列,則將_head指向新節點
  if self.is_empty():
    self.__head = node
  # 若不為空,則找到尾部,將尾節點的next指向新節點
  else:
    cur = self.__head
    while cur.next != None:
      cur = cur.next
    cur.next = node

指定位置新增元素


def insert(self, pos, item):
  """指定位置新增元素"""
  # 若指定位置pos為第一個元素之前,則執行頭部插入
  if pos <= 0:
  self.add(item)
  # 若指定位置超過連結串列尾部,則執行尾部插入
  epf pos > (self.length()-1):
  self.append(item)
  # 找到指定位置
  else:
    node = Node(item)
    count = 0
    # pre用來指向指定位置pos的前一個位置pos-1,初始從頭節點開始移動到指定位置
    pre = self.__head
    while count < (pos-1):
      count  = 1
      pre = pre.next
    # 先將新節點node的next指向插入位置的節點
    node.next = pre.next
    # 將插入位置的前一個節點的next指向新節點
    pre.next = node

刪除節點


def remove(self,item):
  """刪除節點"""
  cur = self.__head
  pre = None
  while cur != None:
  # 找到了指定元素
  if cur.item == item:
    # 如果第一個就是刪除的節點
    if not pre:
      # 將頭指標指向頭節點的後一個節點
      self.__head = cur.next
    else:
      # 將刪除位置前一個節點的next指向刪除位置的後一個節點
      pre.next = cur.next
      break
    else:
      # 繼續按連結串列後移節點
      pre = cur
      cur = cur.next

查詢節點是否存在


def search(self,item):
  """連結串列查詢節點是否存在,並返回True或者False"""
  cur = self.__head
  while cur != None:
    if cur.item == item:
      return True
      cur = cur.next
    return False

以上這篇python資料結構連結串列之單向連結串列(例項講解)就是小編分享給大家的全部內容了,希望能給大家一個參考,也希望大家多多支援指令碼之家。

您可能感興趣的文章:

python單連結串列實現程式碼例項Python單連結串列的簡單實現方法Python單連結串列簡單實現程式碼Python資料結構之單連結串列詳解Python資料結構與演算法之連結串列定義與用法例項詳解【單連結串列、迴圈連結串列】單連結串列反轉python實現程式碼示例淺談Python單向連結串列的實現Python實現的單向迴圈連結串列功能示例Python資料結構與演算法之列表(連結串列,linked list)簡單實現python實現單向連結串列詳解Python實現針對給定單連結串列刪除指定節點的方法

相關文章

程式語言 最新文章