上篇文章说到了单链表,这次是双链表,单链表可参考文章末尾链接。
它包含了三个域,一个用于存储上一个节点的地址(直接前驱),一个用于数据存储,一个指向下一个节点(直接后继),而最后一个节点的直接后继指向None,最前面的直接前驱指向None。
链表包含:单向链表、双向链表、循环链表、块状链表
链表中双向链表结构图:
实践代码:
# -*- encoding: utf-8 -*-
"""
@File : doubleLinkedList
@Author : TopAbu.com
@Software: IntelliJ IDEA
"""
class Node(object):
name = '节点类'
def __init__(self, item):
self.item = item
self.pre = None
self.next = None
def __repr__(self):
return str(self.item)
class DoubleLinkedList(object):
name = '双向链表'
def __init__(self):
self.__head = None
def is_empty(self):
'''判断是否为空'''
return self.__head is None
def length(self):
'''返回链表长度'''
cur = self.__head
count = 0
while cur is not None:
count += 1
cur = cur.next
return count
def travel(self):
'''遍历链表,返回链表所有item'''
cur = self.__head
while cur is not None:
print(cur.item)
cur = cur.next
def search(self, item):
'''查找某一参数是否在列表中'''
cur = self.__head
while cur is not None:
if cur.item == item:
return True
cur = cur.next
return False
def add(self, item):
'''
向链表头部增加元素
链表中的head指向新增加的节点
新节点指向后续节点
后续节点指向新节点
'''
node = Node(item)
node.next = self.__head
if self.__head is not None:
self.__head.pre = node
self.__head = node
def append(self, item):
'''向链表尾部添加节点'''
node = Node(item)
if self.is_empty():
self.__head = node
return
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = node
node.pre = cur
def insert(self, item, position):
'''在指定位置添加一个元素'''
if position <= 0:
self.add(item)
elif position > (self.length() - 1):
self.append(item)
else:
count = 0
cur = self.__head
node = Node(item)
while count < position:
cur = cur.next
count += 1
node.next = cur
node.pre = cur.pre
cur.pre.next = node
cur.pre = node
def remove(self, item):
'''删除链表中的元素'''
cur = self.__head
pre = None
while cur is not None:
if cur.item == item:
if cur == self.__head:
self.__head = cur.next
else:
if cur.next:
cur.next.pre = cur.pre
cur.pre.next = cur.next
cur.pre = None
cur.next = None
return
pre = cur
cur = cur.next
if __name__ == '__main__':
dl = DoubleLinkedList()
print(dl.is_empty())
dl.add(1)
dl.travel()
print(dl.is_empty())
dl.add('a')
dl.travel()
print('*'*20)
dl.append('last')
dl.travel()
print('*'*20)
dl.insert('topabu.com', 2)
dl.travel()
print('*'*20)
dl.remove('last')
dl.travel()
参考链接:python链表之单向链表实践
文章评论