淺談Python單向鏈表的實現(xiàn)

更新時間：2015年12月24日 11:21:16 投稿：hebedich

本文給大家簡單介紹了下鏈表的知識，然后用Python模擬一下單鏈表，比較簡單，初學者可以參考參考，大神可以給我點改進意見

鏈表由一系列不必在內(nèi)存中相連的結構構成，這些對象按線性順序排序。每個結構含有表元素和指向后繼元素的指針。最后一個單元的指針指向NULL。為了方便鏈表的刪除與插入操作，可以為鏈表添加一個表頭。

刪除操作可以通過修改一個指針來實現(xiàn)。

插入操作需要執(zhí)行兩次指針調(diào)整。

1. 單向鏈表的實現(xiàn)

1.1 Node實現(xiàn)

每個Node分為兩部分。一部分含有鏈表的元素，可以稱為數(shù)據(jù)域；另一部分為一指針，指向下一個Node。

class Node():
  __slots__=['_item','_next']  #限定Node實例的屬性
  def __init__(self,item):
    self._item=item
    self._next=None   #Node的指針部分默認指向None
  def getItem(self):
    return self._item
  def getNext(self):
    return self._next
  def setItem(self,newitem):
    self._item=newitem
  def setNext(self,newnext):
    self._next=newnext

1.2 SinglelinkedList的實現(xiàn)

class SingleLinkedList(): 
  def __init__(self):
    self._head=None  #初始化鏈表為空表
    self._size=0

1.3 檢測鏈表是否為空

def isEmpty(self):
  return self._head==None

1.4 add在鏈表前端添加元素

def add(self,item):
  temp=Node(item)
  temp.setNext(self._head)
  self._head=temp

1.5 append在鏈表尾部添加元素

def append(self,item):
  temp=Node(item)
  if self.isEmpty():
    self._head=temp  #若為空表，將添加的元素設為第一個元素
  else:
    current=self._head
    while current.getNext()!=None:
      current=current.getNext()  #遍歷鏈表
    current.setNext(temp)  #此時current為鏈表最后的元素

1.6 search檢索元素是否在鏈表中

def search(self,item):
  current=self._head
  founditem=False
  while current!=None and not founditem:
    if current.getItem()==item:
      founditem=True
    else:
      current=current.getNext()
  return founditem

1.7 index索引元素在鏈表中的位置

def index(self,item):
  current=self._head
  count=0
  found=None
  while current!=None and not found:
    count+=1
    if current.getItem()==item:
      found=True
    else:
      current=current.getNext()
  if found:
    return count
  else:
    raise ValueError,'%s is not in linkedlist'%item

1.8 remove刪除鏈表中的某項元素

def remove(self,item):
  current=self._head
  pre=None
  while current!=None:
    if current.getItem()==item:
      if not pre:
        self._head=current.getNext()
      else:
        pre.setNext(current.getNext())
      break
    else:
      pre=current
      current=current.getNext()

1.9 insert鏈表中插入元素

def insert(self,pos,item):
  if pos<=1:
    self.add(item)
  elif pos>self.size():
    self.append(item)
  else:
    temp=Node(item)
    count=1
    pre=None
    current=self._head
    while count<pos:
      count+=1
      pre=current
      current=current.getNext()
    pre.setNext(temp)
    temp.setNext(current)

全部代碼

class Node():
  __slots__=['_item','_next']
  def __init__(self,item):
    self._item=item
    self._next=None
  def getItem(self):
    return self._item
  def getNext(self):
    return self._next
  def setItem(self,newitem):
    self._item=newitem
  def setNext(self,newnext):
    self._next=newnext
     
class SingleLinkedList(): 
  def __init__(self):
    self._head=None #初始化為空鏈表
  def isEmpty(self):
    return self._head==None
  def size(self):
    current=self._head
    count=0
    while current!=None:
      count+=1
      current=current.getNext()
    return count
  def travel(self):
    current=self._head
    while current!=None:
      print current.getItem()
      current=current.getNext()
  def add(self,item):
    temp=Node(item)
    temp.setNext(self._head)
    self._head=temp
 
  def append(self,item):
    temp=Node(item)
    if self.isEmpty():
      self._head=temp  #若為空表，將添加的元素設為第一個元素
    else:
      current=self._head
      while current.getNext()!=None:
        current=current.getNext()  #遍歷鏈表
      current.setNext(temp)  #此時current為鏈表最后的元素
  def search(self,item):
    current=self._head
    founditem=False
    while current!=None and not founditem:
      if current.getItem()==item:
        founditem=True
      else:
        current=current.getNext()
    return founditem
  def index(self,item):
    current=self._head
    count=0
    found=None
    while current!=None and not found:
      count+=1
      if current.getItem()==item:
        found=True
      else:
        current=current.getNext()
    if found:
      return count
    else:
      raise ValueError,'%s is not in linkedlist'%item       
  def remove(self,item):
    current=self._head
    pre=None
    while current!=None:
      if current.getItem()==item:
        if not pre:
          self._head=current.getNext()
        else:
          pre.setNext(current.getNext())
        break
      else:
        pre=current
        current=current.getNext()           
  def insert(self,pos,item):
    if pos<=1:
      self.add(item)
    elif pos>self.size():
      self.append(item)
    else:
      temp=Node(item)
      count=1
      pre=None
      current=self._head
      while count<pos:
        count+=1
        pre=current
        current=current.getNext()
      pre.setNext(temp)
      temp.setNext(current)
 
if __name__=='__main__':
  a=SingleLinkedList()
  for i in range(1,10):
    a.append(i)
  print a.size()
  a.travel()
  print a.search(6)
  print a.index(5)
  a.remove(4)
  a.travel()
  a.insert(4,100)
  a.travel()

您可能感興趣的文章:

Pytest自動化測試的具體使用
Pytest是一個Python的自動化測試框架,它可用于編寫單元測試、功能測試、集成測試和端到端測試,本文就來介紹一下Pytest自動化測試的具體使用,感興趣的可以了解一下
2024-01-01
Python 3中的yield from語法詳解
在python 3.3里，generator新增了一個語法 yield from，這個yield from的作用是什么？語法是什么呢？下面通過這篇文章主要給大家詳細介紹了Python 3中yield from語法的相關資料，需要的朋友可以參考借鑒，下面來一起看看吧。
2017-01-01
python的paramiko模塊基本用法詳解
paramiko 是一個用于在Python中執(zhí)行遠程操作的模塊,支持SSH協(xié)議,它可以用于連接到遠程服務器,執(zhí)行命令、上傳和下載文件,以及在遠程服務器上執(zhí)行各種操作,這篇文章主要介紹了python的paramiko模塊基本用法,需要的朋友可以參考下
2023-08-08
NumPy之矩陣向量線性代數(shù)等操作示例
這篇文章主要為大家介紹了NumPy之矩陣向量線性代數(shù)等操作示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
2023-04-04
Python實現(xiàn)號碼歸屬地查詢功能
這篇文章主要為大家詳細介紹了如何利用Python實現(xiàn)對手機號碼進行地域分析并查詢歸屬地的功能，感興趣的小伙伴可以跟隨小編一起學習一下
2022-12-12
Flask中提供靜態(tài)文件的實例講解
在本篇文章里小編給大家分享的是一篇關于Flask中提供靜態(tài)文件的實例及相關知識點詳解，有興趣的朋友們可以跟著學習下。
2021-12-12
python標記語句塊使用方法總結
在本篇文章里小編給大家整理了關于python標記語句塊使用方法以及相關知識點，需要的朋友們參考下。
2019-08-08
Python構造函數(shù)及解構函數(shù)介紹
這篇文章主要介紹了Python構造函數(shù)及解構函數(shù)介紹,本文只是講解構造及解構函數(shù)的簡單知識,需要的朋友可以參考下
2015-02-02
Pytorch 神經(jīng)網(wǎng)絡—自定義數(shù)據(jù)集上實現(xiàn)教程
今天小編就為大家分享一篇Pytorch 神經(jīng)網(wǎng)絡—自定義數(shù)據(jù)集上實現(xiàn)教程，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2020-01-01
詳解Django中間件的5種自定義方法
這篇文章主要介紹了詳解Django中間件的5種自定義方法,小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2018-07-07