雙向鏈表
雙向鏈表又叫做雙鏈表，每個(gè)節(jié)點(diǎn)有兩個(gè)指針域和一個(gè)數(shù)據(jù)域。prev指針域指向前一個(gè)節(jié)點(diǎn)，next指針域指向下一個(gè)節(jié)點(diǎn)。注意，第一個(gè)節(jié)點(diǎn)的prev指針域指向空值，最后一個(gè)節(jié)點(diǎn)的next域也是指向空值。
雙鏈表的主要操作跟單鏈表一樣，具有如下操作
1. is_empty() 鏈表是否為空
2. length() 鏈表長度
3. travel() 遍歷整個(gè)鏈表
4. add(item) 鏈表頭部添加元素
5.? append(item) 鏈表尾部添加元素
6.? insert(pos, item) 指定位置添加元素
7. remove(item) 刪除節(jié)點(diǎn)
8. search(item) 查找節(jié)點(diǎn)是否存在
python 實(shí)現(xiàn)：
#_*_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 作為類內(nèi)部使用，對(duì)外不可見'''
? ? ? ? self.__head = node
? ? def is_empty(self):
? ? ? ? '''判斷鏈表是否為空'''
? ? ? ? return self.__head is None
? ? def length(self):
? ? ? ? '''鏈表的長度'''
? ? ? ? #特別要考慮當(dāng)鏈表是空的情況
? ? ? ? # cur游標(biāo)，用來移動(dòng)遍歷節(jié)點(diǎn)
? ? ? ? cur = self.__head
? ? ? ? count = 0
? ? ? ? while cur != None:
? ? ? ? ? ? count += 1
? ? ? ? ? ? cur = cur.next
? ? ? ? return count
? ? def travel(self):
? ? ? ? '''遍歷整個(gè)鏈表'''
? ? ? ? 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
? ? ? ? #如果鏈表是空，則將頭節(jié)點(diǎn)直接指向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):
? ? ? ? '''刪除某個(gè)元素的節(jié)點(diǎn)'''
? ? ? ? cur = self.__head
? ? ? ? while cur != None :
? ? ? ? ? ? if cur.item == item:
? ? ? ? ? ? ? ? #先判斷此節(jié)點(diǎn)是否為頭節(jié)點(diǎn)
? ? ? ? ? ? ? ? if cur == self.__head:
? ? ? ? ? ? ? ? ? ? self.__head = cur.next
? ? ? ? ? ? ? ? ? ? if cur.next:
? ? ? ? ? ? ? ? ? ? ? ? #要判斷鏈表是否只有一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = None
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? cur.prev.next = cur.next
? ? ? ? ? ? ? ? ? ? if cur.next:
? ? ? ? ? ? ? ? ? ? ? ? #如果刪除的不是最后一個(gè)節(jié)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev
? ? ? ? ? ? ? ? break
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? cur = cur.next
? ? def search(self, item):
? ? ? ? ''' 查找節(jié)點(diǎn)是否存在'''
? ? ? ? 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()
運(yùn)行結(jié)果：
True
0
1 2
3 1 2
3 1 4 2
True
3 1 4 2
3 1 4
```
