Python是如何实现单链表和双向链表的？-创新互联

Python是如何实现单链表和双向链表的？相信很多新手小白还没学会这个技能，通过这篇文章的总结，希望你能学会。如下资料是实现单链表和双向链表的代码。

单链表：

# -*- coding:utf-8 -*-
class Node(object):
   """节点"""
   def __init__(self,elem):
     self.elem = elem
     self.next = None

class SingleLinkList(object):
   """单链表"""
   #头结点
   def __init__(self,node = None):
     self._head = node
   def is_empty(self):
     if self._head == None:
       return True
     else :
       return False
   def length(self):
     cur = self._head
     count = 0
     while cur != None:
       cur = cur.next
       count += 1
     return count
   def travel(self):
     """遍历整个链表"""
     cur = self._head
     if cur == None:
       return
     count = 0
     while cur != None:
       print(cur.elem,end=" ")
       cur = cur.next
       count += 1
     return count
   def add(self,item):
     """链表头部添加元素"""
     node =Node(item)
     node.next = self._head
     self._head = node
   def append(self,item):
     """链表尾部添加元素,叫尾插法"""
     node = Node(item)
     if self.is_empty():
       self._head = node
     else:
       cur = self._head
       while cur.next !=None:
         cur = cur.next
       cur.next = node
   def insert(self,pos,item):
     """指定位置添加元素
     :param pos 从0开始
     """
     if pos <= 0:
       self.add(item)
     elif pos >= self.length():
       self.append(item)
     else :
       pre = self._head
       count = 0
       while count <= pos -1:
         pre = pre.next
         count += 1
       node = Node(item)
       node.next = pre.next
       pre.next = node
   def remove(self,item):
     """删除指定的节点"""
     cur = self._head
     pre = None
     while cur != None:
       if cur.elem == item:
         #判断是否为头结点
         if cur == self._head:
           self._head = cur.next
           break
         else :
           pre.next = cur.next
           break
       else :
         pre = cur
         cur = cur.next
   def search(self,item):
     """查找节点是否存在"""
     cur = self._head
     while cur != None:
       if cur.elem == item:
         return  True
       else :
         cur = cur.next
     return False

if __name__ == "__main__":
   single_obj = SingleLinkList()
   print(single_obj.is_empty())   #True

     print(single_obj.length())     #0
   single_obj.append(1)
   print(single_obj.is_empty())
   print(single_obj.length())

   single_obj.append(2)
   single_obj.add(8)
   single_obj.append(3)
   single_obj.append(4)
   single_obj.append(5)
   single_obj.append(6)
   single_obj.travel()    #8 1 2 3 4 5 6
   print(" ")
   single_obj.insert(-1,9)
   single_obj.travel()    #9 8 1 2 3 4 5 6
   print(" ")
   single_obj.insert(5,100)
   single_obj.travel()    #9 8 1 2 3 4 100 5 6
   print(" ")
   single_obj.insert(10,200)
   single_obj.travel()    #9 8 1 2 3 4 100 5 6 200
   print(" ")
   single_obj.remove(200)
   single_obj.travel()    # 9 8 1 2 3 4 100 5 6

双向链表：

# -*- coding:utf-8 -*-
class Node(object):
   """节点"""
   def __init__(self,item):
     self.elem = item
     self.prev = None
     self.next = None

class Double_linked_list(object):
   """双链表"""
   def __init__(self,node = None):
     self._head = node
   def is_empty(self):
     if self._head is None:
       return True
     else:
       return False
   def length(self):
     cur = self._head
     count = 0
     while cur != None:
       cur = cur.next
       count += 1
     return count
   def travel(self):
     """遍历整个链表"""
     cur = self._head
     if cur == None:
       return
     count = 0
     while cur != None:
       print(cur.elem,end=" ")
       cur = cur.next
       count += 1
     return count
   def add(self,item):
     """链表头部添加元素"""
     node =Node(item)
     node.next = self._head
     self._head = node
     node.next.prev = node
   def append(self,item):
     """链表尾部添加元素,叫尾插法"""
     node = Node(item)
     if self.is_empty():
       self._head = node
     else:
       cur = self._head
       while cur.next !=None:
         cur = cur.next
       cur.next = node
       node.prev = cur
   def insert(self,pos,item):
     """指定位置添加元素
     :param pos 从0开始
     """
     if pos <= 0:
       self.add(item)
     elif pos >= self.length():
       self.append(item)
     else :
       cur = self._head
       count = 0
       while count < pos :
         cur = cur.next
         count += 1
       node = Node(item)
       node.next = cur
       node.prev = cur.prev
       cur.prev.next = node
       cur.prev = node
   def remove(self,item):
     """删除指定的节点"""
     cur = self._head
     while cur != None:
       if cur.elem == item:
         #判断是否为头结点
         if cur == self._head:
           self._head = cur.next
           if cur.next:
             #判断链表是否只有一个节点
             cur.next.prev = None
           break
         else :
           cur.prev.next = cur.next
           if cur.next:
             cur.next.prev = cur.prev
           break
       else :
         pre = cur
         cur = cur.next
   def search(self,item):
     """查找节点是否存在"""
     cur = self._head
     while cur != None:
       if cur.elem == item:
         return  True
       else :
         cur = cur.next
     return False

if __name__ == "__main__":
   linkl = Double_linked_list()
   print(linkl.is_empty())
   print(linkl.length())

   linkl.append(1)
   print(linkl.is_empty())
   print(linkl.length())

   linkl.append(2)
   linkl.add(8)
   linkl.append(3)
   linkl.append(4)
   linkl.append(5)
   linkl.append(6)
   linkl.travel()    #8 1 2 3 4 5 6
   print(" ")
   linkl.insert(-1,9)
   linkl.travel()    #9 8 1 2 3 4 5 6
   print(" ")
   linkl.insert(5,100)
   linkl.travel()    #9 8 1 2 3 4 100 5 6
   print(" ")
   linkl.insert(10,200)
   linkl.travel()    #9 8 1 2 3 4 100 5 6 200
   print(" ")
   linkl.remove(200)
   linkl.travel()    # 9 8 1 2 3 4 100 5 6

以上就是实现单链表和双向链表的代码，详细使用情况还需要大家自己亲自动手使用过才能领会。如果想了解更多相关内容，欢迎关注创新互联行业资讯频道！

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。