python-实现双链表

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

双链表和单链表进行比较的优点与不同

节点多了一个前驱指针域
在很多基本操作上，多了一种选择，因为双链表可以向前进行移动寻位
如果给每个节点添加一个对应的下标，那么在寻找节点时，我们可以使用二分发来进行节点的寻址工作，这相对于单链表是一个性能的优化

 7  """

  8  python实现双链表

  9  """

 10 class Node(object):

 11     def __init__(self,elem):

 12         self.elem = elem

 13         self.next = None

 14         self.front = None

 15 class linklist(object):

 16     def __init__(self,node = None):#链表的初始化

 17         self.__head = node

 18         self.curlen = 0

 19     def empty(self):

 20         if self.head == None:

 21             raise Exception("链表为空")

 22     def len(self):

 23         return self.curlen

 24     def add_head(self,item):

 25         node = Node(item)

 26         node.next = self.__head

 27         self.__head = node

 28         self.curlen += 1

 29     def add_tail(self,item):

 30         node = Node(item)

 31         tempnode = self.__head

 32         while tempnode != None:

 33             tempnode = tempnode.next

 34         tempnode.next = node

 35         self.curlen += 1

 36     def insert(self,location,item):

 37         node = Node(item)

 38         if location < 0 or location > self.curlen - 1:

 39             raise Exception("插入位置非法")

 40         elif location == 0:

 41             self.add_head(item)

 42         elif location == self.curlen:

 43             tempnode = self.__head

 44             while tempnode.next != None:

 45                 tempnode = tempnode.next

 46             tempnode.next = node

 47             self.curlen += 1

 48         else:

 49             tempnode = self.__head

 50             for i in range(location - 1):

 51                 tempnode = tempnode.next

 52             node.next = tempnode.next

 53             tempnode.next = node

 54             self.curlen += 1

 55     def delitem(self,item):

 56         if self.__head.elem == item:

 57             self.__head = self.__head.next

 58         else:

 59             tempnode = self.__head

 60

 61             while tempnode!= None:

 62                 if tempnode.next.elem == item:

 63                     break

 64                 tempnode = tempnode.next

 65             tempnode.next = tempnode.next.next

 66     def change(self,item,changed_item):

 67         tempnode = self.__head

 68         while tempnode != None:

 69             if tempnode.elem == item:

 70                 tempnode.elem = changed_item

 71                 break

 72     def search(self,item):

 73         tempnode = self.__head

 74         while tempnode != None:

 75             if tempnode.elem == item:

 76                 return True

77             tempnode = tempnode.next

 78         return False

 79     def display(self):

 80         tempnode = self.__head

 81         while tempnode != None:

 82             print(tempnode.elem,end = " ")

 83             tempnode = tempnode.next

 84         print()

 85 if __name__ == "__main__":

 86     linklist1 = linklist()

 87     linklist1.add_head(1)

 88     linklist1.add_head(2)

 89     linklist1.insert(0,3)

 90     linklist1.display()

 91     print(linklist1.curlen)

 92     linklist1.delitem(2)

 93     linklist1.display()

 94     linklist1.change(3,4)

 95     print(linklist1.search(4))

 96     linklist1.display()