双向链表
双向链表又叫做双链表，每个节点有两个指针域和一个数据域。prev指针域指向前一个节点，next指针域指向下一个节点。注意，第一个节点的prev指针域指向空值，最后一个节点的next域也是指向空值。
双链表的主要操作跟单链表一样，具有如下操作
- is_empty() 链表是否为空
- length() 链表长度
- travel() 遍历整个链表
- add(item) 链表头部添加元素
- append(item) 链表尾部添加元素
- insert(pos, item) 指定位置添加元素
- remove(item) 删除节点
- search(item) 查找节点是否存在
python 实现：
#_*_coding:utf-8_*_
class Node(object):
def __init__(self, item):
self.item = item
self.prev = None
self.next = None
class DoubleLinkList(object):
def __init__(self, node=None):
'''_head 作为类内部使用，对外不可见'''
self.__head = node
def is_empty(self):
'''判断链表是否为空'''
return self.__head is None
def length(self):
'''链表的长度'''
#特别要考虑当链表是空的情况
# cur游标，用来移动遍历节点
cur = self.__head
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def travel(self):
'''遍历整个链表'''
cur = self.__head
if cur == None:
print("empty linklist")
return
while cur != None:
print(cur.item, end=' ')
cur = cur.next
print('')
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)
cur = self.__head
#如果链表是空，则将头节点直接指向Node
if self.is_empty():
self.__head = node
else:
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() -1):
self.append(item)
else:
cur = self.__head
count = 0
while count < pos:
count += 1
cur = cur.next
node = Node(item)
node.next = cur
cur.prev.next = node
cur.prev = node
node.prev = cur.prev
def remove(self, item):
'''删除某个元素的节点'''
cur = self.__head
while cur != None :
if cur.item == item:
#先判断此节点是否为头节点
if cur == self.__head:
self.__head = cur.next
if cur.next:
#要判断链表是否只有一个节点
cur.next.prev = None
else:
cur.prev.next = cur.next
if cur.next:
#如果删除的不是最后一个节点
cur.next.prev = cur.prev
break
else:
cur = cur.next
def search(self, item):
''' 查找节点是否存在'''
cur = self.__head
while cur != None:
if cur.item == item:
return True
else:
cur = cur.next
return False
if __name__ == '__main__':
ll = DoubleLinkList()
print(ll.is_empty())
print(ll.length())
ll.append(1)
ll.append(2)
ll.travel()
ll.add(3)
ll.travel()
ll.insert(2, 4)
ll.travel()
print(ll.search(3))
ll.travel()
ll.remove(2)
ll.travel()运行结果：
True
0
1 2
3 1 2
3 1 4 2
True
3 1 4 2
3 1 4 2020年最新Python教程：
如果你处于想学Python或者正在学习Python，Python的教程不少了吧，但是是最新的吗？
说不定你学了可能是两年前人家就学过的内容，在这小编分享一波2020最新的Python教程。
以上这些教程小编已经为大家打包准备好了，希望对正在学习的你有所帮助！
获取方式，私信小编 “ 资料 ”，即可免费获取哦！
本文来自投稿，不代表本人立场，如若转载，请注明出处：http://www.souzhinan.com/kj/362719.html