链表（单链表、双链表）

前言：链表是算法中比较难理解的部分，本博客记录单链表、双链表学习，理解节点和指针的使用，主要内容包括：使用python创建链表、实现链表常见的操作。

目录

单链表

双链表

---

单链表

引入链表的背景：

先来看一下数据，数组是一块连续的区域，需要预留空间。

链表，是一种线性表，线性表包括顺序表、链表，但链表不像顺序表一样连续地存储数据，而是在每个节点里存放下一个节点的位置信息（地址）。

单链表，第一个节点是头节点，最后一个节点是尾节点。

操作链表时，需要注意特殊的情况：

1. 空链表
2. 只有一个头节点没有尾节点的链表，头节点地址指向空
3. 有一个头节点，接着连接一个尾节点，没有中间节点

使用python语言创建一个单链表

需要实现以下功能：

• 实现判断链表是否为空
• 计算链表的长度
• 在链表头部添加元素
• 在链表尾部添加元素
• 在链表的指定位置添加元素
• 删除指定元素的节点
• 判断节点是否存在

class Node(object):def __init__(self, elem):# 节点self.elem = elemself.next = None# 单链表
class SingleLinkList(object):def __init__(self, node=None):self.__head = node# 判断链表是否为空def is_empty(self):return self.__head == None# 链表的长度def length(self):# cur游标用来遍历节点cur = self.__headcount = 1while cur != None:count += 1cur = cur.nextreturn count# 链表的遍历def travel(self):cur = self.__headwhile cur != None:print(cur.elem, end=" ")cur = cur.next# 头部添加元素def add(self, item):node = Node(item)node.next = self.__headself.__head = node# 尾部添加元素def append(self, item):node = Node(item)if self.is_empty():self.__head = nodeelse:cur = self.__headwhile cur.next != None:cur = cur.nextcur.next = nodepass# 指定位置添加元素def insert(self, pos, item):if pos <= 0:self.add(item)elif pos > (self.length() - 1):self.append(item)else:pre = self.__headcount = 0while count < (pos - 1):count += 1pre = pre.next#     当循环退出后 pre指向pos-1node = Node(item)node.next = pre.nextpre.next = node# 删除元素 找到具体的数据删除def remove(self, item):cur = self.__headpre = Nonewhile cur != None:if cur.elem == item:if cur == self.__head:self.__head = cur.nextelse:pre.next = cur.nextbreakelse:pre = curcur = cur.next# 查找节点是否存在def search(self, item):cur = self.__headwhile cur != None:if cur.elem == item:return Trueelse:cur = cur.nextreturn False

双链表

双链表比单链表多了个前驱节点

使用python语言创建一个双链表

需要实现以下功能：

• 实现判断链表是否为空
• 计算链表的长度
• 在链表头部添加元素
• 在链表尾部添加元素
• 在链表的指定位置添加元素
• 删除指定元素的节点
• 判断节点是否存在

 

class Node(object):def __init__(self, item):self.elem = itemself.next = Noneself.prev = Noneclass DoubleLinkList(object):# 双链表def __init__(self, node=None):self.__head = node# 判断链表是否为空def is_empty(self):return self.__head == None# 链表的长度def length(self):# cur游标用来遍历节点cur = self.__headcount = 1while cur != None:count += 1cur = cur.nextreturn count# 链表的遍历def travel(self):cur = self.__headwhile cur != None:print(cur.elem, end=" ")cur = cur.next# 头部添加元素def add(self, item):node = Node(item)node.next = self.__headself.__head = nodenode.next.prev = node# 尾部添加元素def append(self, item):node = Node(item)if self.is_empty():self.__head = nodeelse:cur = self.__headwhile cur.next != None:cur = cur.nextcur.next = nodenode.prev = curpass# 指定位置添加元素def insert(self, pos, item):if pos <= 0:self.add(item)elif pos > (self.length() - 1):self.append(item)else:cur = self.__headcount = 0while count < (pos - 1):count += 1cur = cur.next#     当循环退出后 pre指向posnode = Node(item)node.next = curnode.prev = cur.prevcur.prev.next = nodecur.prev = node# 删除元素 找到具体的数据删除def remove(self, item):cur = self.__headwhile cur != None:if cur.elem == item:if cur == self.__head:self.__head = cur.nextif cur.next:# 判断链表是否只有一个节点cur.next.prev = Noneelse:cur.prev.next = cur.nextif cur.next:cur.next.prev = cur.prevbreakelse:cur = cur.next# 查找节点是否存在def search(self, item):cur = self.__headwhile cur != None:if cur.elem == item:return Trueelse:cur = cur.nextreturn False