python數(shù)據(jù)結(jié)構(gòu)鏈表之單向鏈表(實(shí)例講解)

單向鏈表

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

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

鏈接域next用來(lái)存放下一個(gè)節(jié)點(diǎn)的位置（python中的標(biāo)識(shí)）

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

節(jié)點(diǎn)實(shí)現(xiàn)

class Node(object):
 """單鏈表的結(jié)點(diǎn)"""
 def __init__(self,item):
  # item存放數(shù)據(jù)元素
  self.item = item
  # next是下一個(gè)節(jié)點(diǎn)的標(biāo)識(shí)
  self.next = None

單鏈表的操作

is_empty() 鏈表是否為空

length() 鏈表長(zhǎng)度

travel() 遍歷整個(gè)鏈表

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

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

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

remove(item) 刪除節(jié)點(diǎn)

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

單鏈表的實(shí)現(xiàn)

class Singlepnkpst(object):
 """單鏈表"""
 def __init__(self):
  self.__head = None
 
 def is_empty(self):
  """判斷鏈表是否為空"""
  return self.__head == None
 
 def length(self):
  """鏈表長(zhǎng)度"""
  # cur初始時(shí)指向頭節(jié)點(diǎn)
  cur = self.__head
  count = 0
  # 尾節(jié)點(diǎn)指向None，當(dāng)未到達(dá)尾部時(shí)
  while cur != None:
   count += 1
   # 將cur后移一個(gè)節(jié)點(diǎn)
   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):
　　"""頭部添加元素"""
　　# 先創(chuàng)建一個(gè)保存item值的節(jié)點(diǎn)
　　node = Node(item)
　　# 將新節(jié)點(diǎn)的鏈接域next指向頭節(jié)點(diǎn)，即_head指向的位置
　　node.next = self.__head
　　# 將鏈表的頭_head指向新節(jié)點(diǎn)
　　self.__head = nod

尾部添加元素    
def append(self, item):
　　"""尾部添加元素"""
　　node = Node(item)
　　# 先判斷鏈表是否為空，若是空鏈表，則將_head指向新節(jié)點(diǎn)
　　if self.is_empty():
　　　　self.__head = node
　　# 若不為空，則找到尾部，將尾節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
　　else:
　　　　cur = self.__head
　　　　while cur.next != None:
　　　　　　cur = cur.next
　　　　cur.next = node

指定位置添加元素

def insert(self, pos, item):
　　"""指定位置添加元素"""
　　# 若指定位置pos為第一個(gè)元素之前，則執(zhí)行頭部插入
　　if pos <= 0:
 　　self.add(item)
　　# 若指定位置超過(guò)鏈表尾部，則執(zhí)行尾部插入
　　epf pos > (self.length()-1):
 　　self.append(item)
　　# 找到指定位置
　　else:
　　　　node = Node(item)
　　　　count = 0
　　　　# pre用來(lái)指向指定位置pos的前一個(gè)位置pos-1，初始從頭節(jié)點(diǎn)開(kāi)始移動(dòng)到指定位置
　　　　pre = self.__head
　　　　while count < (pos-1):
　　　　　　count += 1
　　　　　　pre = pre.next
　　　　# 先將新節(jié)點(diǎn)node的next指向插入位置的節(jié)點(diǎn)
　　　　node.next = pre.next
　　　　# 將插入位置的前一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)
　　　　pre.next = node

刪除節(jié)點(diǎn)

def remove(self,item):
　　"""刪除節(jié)點(diǎn)"""
　　cur = self.__head
　　pre = None
　　while cur != None:
　　# 找到了指定元素
　　if cur.item == item:
　　　　# 如果第一個(gè)就是刪除的節(jié)點(diǎn)
　　　　if not pre:
　　　　　　# 將頭指針指向頭節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
　　　　　　self.__head = cur.next
　　　　else:
　　　　　　# 將刪除位置前一個(gè)節(jié)點(diǎn)的next指向刪除位置的后一個(gè)節(jié)點(diǎn)
　　　　　　pre.next = cur.next
　　　　　　break
　　　　else:
　　　　　　# 繼續(xù)按鏈表后移節(jié)點(diǎn)
　　　　　　pre = cur
　　　　　　cur = cur.next

查找節(jié)點(diǎn)是否存在    
def search(self,item):
　　"""鏈表查找節(jié)點(diǎn)是否存在，并返回True或者False"""
　　cur = self.__head
　　while cur != None:
　　　　if cur.item == item:
　　　　　　return True
　　　　　　cur = cur.next
　　　　return False
以上這篇python數(shù)據(jù)結(jié)構(gòu)鏈表之單向鏈表(實(shí)例講解)就是小編分享給大家的全部?jī)?nèi)容了