双向链表
双向链表又叫做双链表，每个节点有两个指针域和一个数据域。prev指针域指向前一个节点，next指针域指向下一个节点。注意，第一个节点的prev指针域指向空值，最后一个节点的next域也是指向空值。
双链表的主要操作跟单链表一样，具有如下操作
1. is_empty() 链表是否为空
2. length() 链表长度
3. travel() 遍历整个链表
4. add(item) 链表头部添加元素
5. append(item) 链表尾部添加元素
6. insert(pos, item) 指定位置添加元素
7. remove(item) 删除节点
8. 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
node.prev = cur.prev
cur.prev = node
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
```
