1. 简介
一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
双向链表
2. 操作
- is_empty（）判断链表是否为空
- length（）返回链表的长度
- travel（）遍历
- add（elem）在头部添加一个节点
- append（elem）在尾部添加一个节点
- insert（pos，elem）在指定位置pos添加节点
- remove（elem）删除一个节点
- search（elem）查找节点是否存在
3. 三种链表的对比
- 双向链表的节点不同，有next和prev两个指针
- 遍历链表的判断
以获取length长度为例：
| 单向链表 | 单向循环 | 双向链表 |
|---|---|---|
| while cur!=None: | while cur.next!=self.head: | while cur!=None: |
| count+=1 | count+=1 | count+=1 |
| cur=cur.next | cur=cur.next | cur=cur.next |
- 双向链表主要是删除和插入操作比较复杂，需要记住移动四个指针的先后顺序
4. 实现
class Node(object):
def __init__(self,elem):
self.elem=elem
self.prev=None
self.next=None
class DoubleLinkList(object):
def __init__(self):
self.head=None
def is_empty(self):
return self.head==None
def length(self):
cur = self.head
count= 0
while cur!=None:
count+=1
cur=cur.next
return count
def travel(self):
cur =self.head
print("the travel is:",end=" ")
while cur!=None:
print(cur.elem,end=" ")
cur=cur.next
print("")
- 头部插入
def add(self,elem):
node =Node(elem)
if self.is_empty():
self.head=node
else:
#将node的next指向head的头结点
node.next=self.head
#将head的头结点的prev指向node
self.head.prev=node
#将head指向node
self.head=node
- 尾部插入
def append(self,elem):
node =Node(elem)
if self.is_empty():
self.head=node
else:
#移动到链表尾部
cur=self.head
while cur.next!=None:
cur=cur.next
#将尾结点cur的next指向node
cur.next=node
#将node的prev指向cur
node.prev=cur
- 搜索
def search(self,elem):
cur =self.head
while cur!=None:
if cur.elem==elem:
return True
cur=cur.next
return False
-
指定位置插入
指定位置插入
def insert(self,pos,elem):
if pos<=0:
self.add(elem)
elif pos>(self.length()-1):
self.append(elem)
else:
node=Node(elem)
cur=self.head
count=0
# 移动到指定位置的前一个位置
while count<pos-1:
count+=1
cur=cur.next
# 将node的prev指向cur
node.prev=cur
# 将node的next指向cur的下一个节点
node.next=cur.next
# 将cur的下一个节点的prev指向node
cur.next.prev=node
# 将cur的next指向node
cur.next=node
-
删除元素
删除链表
def remove(self,elem):
if self.is_empty():
return
else:
cur=self.head
if cur.elem==elem:
#如果首节点就是要删除的元素
if cur.next==None:
#如果只有这一个节点
self.head==None
else:
#将第二个节点的prev设置为None
cur.next.prev=None
#将head指向第二个节点
self.head=cur.next
return
while cur!=None:
if cur.elem==elem:
#将cur的前一个节点的next指向cur的后一个节点
cur.prev.next=cur.next
#将cur的后一个节点的prev指向cur的前一个节点
cur.next.prev=cur.prev
break
cur=cur.next
4. 测试
if __name__=="__main__":
dl=DoubleLinkList()
dl.add(2)
dl.add(1)
dl.add(0)
dl.append(4)
dl.insert(3,3)
dl.travel()
print("is 3 in the travel %s" %(dl.search(3)))
dl.remove(3)
print("is 3 in the travel %s" % (dl.search(3)))
dl.remove(0)
print("the length is %d"%(dl.length()))
dl.travel()
5. 总结
三种基本的链表算是介绍完了。我觉得数据结构中最先需要入门同时最难的也就是链表了，Python比c++版本要好的多了，没有那么多的*和p，不过当然还是建议把c++的指针弄明白，面试肯定以c++为主。我觉得三种指针学下来，最重要的是理解三种指针的遍历方式，考虑首尾元素的特殊情况，多画图，不要出现断链现象。
