構(gòu)建節(jié)點(diǎn)類

class Node(object):
def init(self,item):
self.elem=item
self.next=None

構(gòu)建鏈表類

class Single_linkList(object):

def __init__(self,node=None):   #構(gòu)造函數(shù),鏈表頭部
    self.__head=node
            
def __str__(self): 
    return ("您所察看的數(shù)據(jù)為單向鏈表，該鏈表的長度為：%d"%(self.length()))        

def is_empty(self):
    """判斷鏈表頭部是否指向空"""
    return self.__head==None

def length(self):
    """遍歷鏈表，求長度"""
    cur=self.__head      ### 使用cur表示當(dāng)前指針
    count=0
    while cur !=None:
        count +=1
        cur = cur.next
    return count
                    
def travle(self):
    """遍歷打印元素"""
    cur=self.__head        
    if self.is_empty():
        return "There is nothing"            
    else:
        while cur !=None:
            print(cur.elem,end="->")
            cur=cur.next
                    
def append(self,item):
    """尾部添加元素"""
    """遍歷節(jié)點(diǎn)"""
    node=Node(item) #構(gòu)造節(jié)點(diǎn)
    cur=self.__head
    if self.__head==None:  #如果連鏈表為空，則將head 指向 append的元素
        self.__head=node 
    else:
        while cur.next != None:
            cur = cur.next
        cur.next=node
            
def insert(self,persition,item):
    """向指定位置添加元素"""
    node=Node(item) #構(gòu)造節(jié)點(diǎn)        
    cur=self.__head        
    count=0
    if persition<=0:    ### 傳入的數(shù)值小于0時(shí)，認(rèn)為是在頭部插入元素
        self.add(item)            
    elif persition>=self.length():
        self.append(item)    ### 數(shù)值大于鏈表長度時(shí)，在尾部追加元素            
    else:
        while cur != None and count <= persition-2:
            count +=1
            cur = cur.next        
        node.next=cur.next
        cur.next=node
    
def add(self,item):
    """向頭部添加元素"""
    node=Node(item) #構(gòu)造節(jié)點(diǎn)
    cur=self.__head
    node.next=cur
    self.__head=node
    
def get_item(self,persition):        
    """獲取指定位置的元素"""        
    cur=self.__head        
    count=1        
    if self.is_empty():    ### 空列表直接返回           
        return "There is nothing"        
    elif persition<0:
        return self.__head.elem            
    elif persition>self.length()-1:       # 遍歷獲取最后一個(gè)元素           
        cur=self.__head        
        while cur.next !=None:
            cur=cur.next
        return cur.elem            
    else:
        while cur != None and count <=persition:
            count +=1
            cur = cur.next
        return cur.elem       
def pop(self):
    """刪除尾部元素"""
    cur=self.__head        
    if self.length()<=1: #如果只有一個(gè)元素或鏈表為空，則直接將鏈表的head指向空
        self.__head=None   
    else:
        while cur.next.next != None:
            cur = cur.next
        cur.next=None
def remove(self,item):            ### 移除第一個(gè)元素容易出現(xiàn)問題，，主要是將鏈表的頭部指向下一個(gè)元素即可
    """移除指定的第一個(gè)元素"""        
    cur=self.__head
    per=self.__head        
    if self.index(item)==0:
        self.__head=cur.next            
    else:
        while cur != None:
            cur=cur.next
            if per.next.elem == item:
                per.next=cur.next
                return
            per=per.next
                      
def pop_n(self,position):
    """移除指定位置的元素"""
    cur=self.__head
    per=self.__head
    count = 1
    if position > self.length()-1:    ### 位置超出鏈表元素個(gè)數(shù)時(shí)，移除最后一個(gè)元素
        position = self.length()-1      
    if position <= 0:    ### 移除首個(gè)元素
        self.__head=cur.next
        return cur.elem        
    else:
        while cur != None:
            cur=cur.next
            if count == position:
                per.next=cur.next
                return cur.elem
            per=per.next
            count += 1

def type(self):
    return "This is a single link list"

def clear(self):
    """清除列表的所有元素"""
    self.__head=None

def index(self,item):
    """返回元素在鏈表中的位置"""
    cur=self.__head
    count=0
    while cur.elem !=item:
        cur = cur.next
        count +=1
    return count