数据结构——双链表

双链表的结构

• 表元素域val用来存放具体的数据。
• 链接域pre用来存放上一个节点的位置。
• 链接域next用来存放下一个节点的位置。

双链表节点实现

class DoubleLinkListNode(object):"""双向链表节点类初始化"""def __init__(self, pre=None, val=None, next=None):self.pre = preself.val = valself.next = next

双链表的实现

class DoubleLinkList(object):"""双向链表实现类"""def __init__(self, *args, **kwargs):self.length = 0self.head = None

图解说明

• is_empty() 链表是否为空
• traversal() 遍历整个链表
• add(item) 链表头部添加元素
• append(item) 链表尾部添加元素
• insert(pos, item) 指定位置添加元素
• remove(item) 删除节点
• search(item) 查找节点是否存在

双链表-头部添加元素（add）

def add(self, value):"""双向链表在头部添加元素"""cur = DoubleLinkListNode(val=value)if self.is_empty():self.head = curelse:self.head.pre = curcur.next = self.headself.head = curself.length += 1

图解说明

双链表-遍历（traversal）

def traversal(self):"""遍历双向链表:return:"""cur_node = self.headwhile cur_node:print(cur_node.val, end=" ")cur_node = cur_node.next

图解说明

双链表-尾部插入元素（append）

def append(self, value):"""双向链表尾部添加:param value::return:"""new_node = DoubleLinkListNode(val=value)if self.is_empty():self.head = new_nodeelse:cur = self.headwhile cur.next:cur = cur.nextcur.next = new_nodenew_node.pre = curself.length += 1

图解说明

双链表-指定位置插入元素（insert）

def insert(self, index, value):"""双向链表指定位置插入元素:param index::param value::return:"""count = 0cur = self.headprint('index==', index)print('self.length', self.length)if index > self.length or index < 0:raise IndexError("DoubleLinkList assignment index out of range")elif index == 0:self.add(value)elif index == self.length:self.append(value)else:new_node = DoubleLinkListNode(value)while count < index:cur = cur.nextcount += 1new_node.pre = curif cur.next:new_node.next = cur.nextcur.next.pre = new_nodecur.next = new_nodeelse:cur.next = new_nodeself.length += 1

图解说明

双链表-查找指定元素（search）

def search(self, value):"""查找指定元素, 返回元素是否存在标识及索引下标:param value::return:"""flag = Falsecount = 0cur = self.headwhile cur != None and cur.val != value:count += 1cur = cur.nextif cur and cur.val == value:flag = Trueelse:raise ValueError("%s is not in sequential list" % value)print('flag: %s, count: %s' % (flag, count))return flag, count

图解说明

双链表-删除元素（remove）

def remove(self, value):"""双向链表移除元素:return:"""cur = self.headwhile cur.next:if cur.val == value:cur.pre.next = cur.nextcur.next.pre = cur.preself.length -= 1del curbreakelse:cur = cur.next

图解说明

双链表-完整代码及测试

# -*- coding:utf-8 -*-class DoubleLinkListNode(object):"""双向链表节点类初始化"""def __init__(self, pre=None, val=None, next=None):self.pre = preself.val = valself.next = nextclass DoubleLinkList(object):"""双向链表实现类"""def __init__(self, *args, **kwargs):self.length = 0self.head = Nonedef is_empty(self):return self.head is Nonedef __len__(self):return self.lengthdef search(self, value):"""查找指定元素, 返回元素是否存在标识及索引下标:param value::return:"""flag = Falsecount = 0cur = self.headwhile cur != None and cur.val != value:count += 1cur = cur.nextif cur and cur.val == value:flag = Trueelse:raise ValueError("%s is not in sequential list" % value)print('flag: %s, count: %s' % (flag, count))return flag, countdef insert(self, index, value):"""双向链表指定位置插入元素:param index::param value::return:"""count = 0cur = self.headprint('index==', index)print('self.length', self.length)if index > self.length or index < 0:raise IndexError("DoubleLinkList assignment index out of range")elif index == 0:self.add(value)elif index == self.length:self.append(value)else:new_node = DoubleLinkListNode(value)while count < index:cur = cur.nextcount += 1new_node.pre = curif cur.next:new_node.next = cur.nextcur.next.pre = new_nodecur.next = new_nodeelse:cur.next = new_nodeself.length += 1def append(self, value):"""双向链表尾部添加:param value::return:"""new_node = DoubleLinkListNode(val=value)if self.is_empty():self.head = new_nodeelse:cur = self.headwhile cur.next:cur = cur.nextcur.next = new_nodenew_node.pre = curself.length += 1def add(self, value):"""双向链表在头部添加元素"""cur = DoubleLinkListNode(val=value)if self.is_empty():self.head = curelse:self.head.pre = curcur.next = self.headself.head = curself.length += 1def traversal(self):"""遍历双向链表:return:"""cur_node = self.headwhile cur_node:print(cur_node.val, end=" ")cur_node = cur_node.nextdef remove(self, value):"""双向链表移除元素:return:"""cur = self.headwhile cur.next:if cur.val == value:cur.pre.next = cur.nextcur.next.pre = cur.preself.length -= 1del curbreakelse:cur = cur.nextdef main():doublelinklist = DoubleLinkList()doublelinklist.append(1)doublelinklist.append(2)doublelinklist.add(3)doublelinklist.append(4)doublelinklist.insert(4, 666)doublelinklist.insert(5, 888)doublelinklist.search(666)doublelinklist.traversal()print()doublelinklist.remove(666)doublelinklist.traversal()if __name__ == '__main__':main()