鏈表由一系列不必在內(nèi)存中相連的結(jié)構(gòu)構(gòu)成，這些對(duì)象按線性順序排序。每個(gè)結(jié)構(gòu)含有表元素和指向后繼元素的指針。最后一個(gè)單元的指針指向NULL。為了方便鏈表的刪除與插入操作，可以為鏈表添加一個(gè)表頭。
刪除操作可以通過(guò)修改一個(gè)指針來(lái)實(shí)現(xiàn)。
插入操作需要執(zhí)行兩次指針調(diào)整。
1. 單向鏈表的實(shí)現(xiàn)
1.1 Node實(shí)現(xiàn)
??? 每個(gè)Node分為兩部分。一部分含有鏈表的元素，可以稱為數(shù)據(jù)域；另一部分為一指針，指向下一個(gè)Node。
class Node():
__slots__=['_item','_next'] #限定Node實(shí)例的屬性
def __init__(self,item):
self._item=item
self._next=None #Node的指針部分默認(rèn)指向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的實(shí)現(xiàn)
class SingleLinkedList():
def __init__(self):
self._head=None #初始化鏈表為空表
self._size=0
1.3 檢測(cè)鏈表是否為空
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 #若為空表，將添加的元素設(shè)為第一個(gè)元素
else:
current=self._head
while current.getNext()!=None:
current=current.getNext() #遍歷鏈表
current.setNext(temp) #此時(shí)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刪除鏈表中的某項(xiàng)元素
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
全部代碼
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 #若為空表，將添加的元素設(shè)為第一個(gè)元素
else:
current=self._head
while current.getNext()!=None:
current=current.getNext() #遍歷鏈表
current.setNext(temp) #此時(shí)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
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
