双链表算法的基本实现

一、双链表的定义

在Python中，我们可以通过定义一个节点类和双链表类来实现双链表。

1. 声明一个节点类

class Node(object):def __init__(self, values):# 节点值self.values = values# 前驱指针self.prior = None# 后驱指针self.next = None

2. 声明一个双链表类

class Linken(object):def __init__(self):# 头结点self.head = None# 尾结点self.tail = None

二、链表的基本操作

1. 判断链表是否为空

def Empty(self):return self.head is None

2. 记数链表的长度

def Length(self):size = 0p = self.headwhile p != None:size += 1p = p.nextreturn size

3. 实现链表的头插法

def InsertHead(self, values):newnode = Node(values)if self.Empty():self.head = newnodeself.tail = self.headelse:self.head.prior = newnodenewnode.next = self.headself.head = newnodereturn 1

4. 实现链表的尾插法

def InsertTail(self, values):newnode = Node(values)if self.Empty():self.head = newnodeself.tail = newnodeelse:self.tail.next = newnodenewnode.prior = self.tailself.tail = newnodereturn 1

5. 实现链表的中间插法

def Insert(self, index, values):if index <= 0:self.InsertHead(values)elif index > self.Length() - 1:self.InsertTail(values)else:newnode = Node(values)p = self.headfor i in range(index - 1):p = p.nextnewnode.prior = p.priornewnode.next = pp.prior.next = newnodep.prior = newnodereturn 1

6. 实现链表的头删法

def DeleteHead(self):if self.Empty():return Noneelif self.head == self.head.next:self.head = Noneself.tail = Noneelse:self.head = self.head.nextself.head.prior = None

7. 实现链表的尾删法

def DeleteTail(self):if self.Empty():return Noneelif self.head == self.tail:self.head = Noneself.tail = Noneelse:self.tail = self.tail.priorself.tail.next = None

8. 实现链表的中间删法

def Delete(self, index):if index <= 0:self.DeleteHead()elif index > self.Length() - 1:self.DeleteTail()else:p = self.headfor i in range(index - 1):p = p.nextp.prior.next = p.nextp.next.prior = p.prior

9. 实现链表的元素的查询

def SelectLinken(self, values):p = self.headwhile p:if p.values == values:print(p.values, end=' ')breakp = p.next

10. 实现链表的内容输出查询

def OutValues(self):p = self.headwhile p:print(p.values, end=' ')p = p.nextprint()

三、运行实例

1.测试代码

if __name__ == '__main__':# 测试以上定义的方法print('-------------------头插法-------------------')linken = Linken()linken.InsertHead(1)linken.InsertHead(2)linken.InsertHead(3)linken.InsertTail(4)linken.Insert(2, 5)linken.OutValues()print('中间删除：')linken.Delete(2)linken.OutValues()print('尾节点删除：')linken.DeleteTail()linken.OutValues()print('头节点删除：')linken.DeleteHead()linken.OutValues()print(linken.SelectLinken(8))print('-------------------尾插法-------------------')linken = Linken()linken.InsertTail(1)linken.InsertTail(2)linken.InsertTail(3)linken.Insert(2, 4)linken.OutValues()print('中间删除：')linken.Delete(2)linken.OutValues()print('尾节点删除：')linken.DeleteTail()linken.OutValues()print('头节点删除：')linken.DeleteHead()linken.OutValues()print(linken.SelectLinken(8))

2.运行展示