单链表
'''
is_empty() 链表是否为空
length() 查询链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos,item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在
'''
class SingleNode(object):
'''单链表的节点'''
def __init__(self,item):
self.item = item
# 数据域
self.next = None
# 指针域next指向下一个节点
def is_empty(self):
'''判断链表是否为空,看头结点是否为空'''
return self._head == None
def length(self):
'''链表长度,遍历链表,每遍历一次就进行加一操作'''
cur = self._head
#令cur当前指向头节点位置
count = 0 #count用来返回单链表长度
while cur != None:
count = count + 1
cur = cur.next #到达下一个指针域
return count
def travel(self):
'''遍历单链表,对遍历到的单链表元素取出数据域输出'''
cur = self._head#指向头结点
while cur != None:
print(cur.item)#输出当前节点的元素
cur = cur.next#指向下一个节点
print(" ")
def add(self,item):
'''在单链表头部添加数据域为item元素的节点,
使包含有item元素的节点的下一个节点为头结点(没进行添加之前的)'''
node = SingleNode(item)
# 创建连接,使头结点为第二个节点
node.next = self._head
# 对头结点进行重新命名
self._head = node
def append(self,item):
'''尾部添加元素,当单链表为空时，直接添加。
当单链表不为空时，在尾部添加(进行遍历操作,直到最后一个节点)'''
# 创建节点元素存放item元素
node = SingleNode(item)
if self.is_empty():#如果链表为空
self._head = node
else:
cur = self._head #令指针指向头结点
while cur.next != None:#进行遍历
cur = cur.next#依次向下进行遍历，直到最后一个节点
cur.next = node#让最后一个节点为node，包含有item的元素的节点
def insert(self,pos,item):
'''在指定pos位置,添加包含有item元素的节点'''
if pos <= 0:
#当pos为小于等于0的位置时，将item添加在头部
self.add(item)
elif pos >= self.length():
# 当pos大于等于链表长度时,将item添加在尾部
self.append(item)
else:#既不在头部,又不在尾部
'''创建pre指针,指向pos的前一个位置'''
node = SingleNode(item)
# 存储item元素的节点
count = 0
# pre用来指向位置pos的前一个位置pos-1，从头结点开始
pre = self._head
while count < pos - 1:
# 当count为pos-1时，pre为要插入位置的前一个节点
count += 1
pre = pre.next
node.next = pre.next #先连接原来链表中pos位置后面节点左面的线
pre.next = node#连接原来链表中前一个节点的右面的线
def remove(self,item):
cur = self._head
pre = None
while cur != None:
# 当单链表不为空时
if cur.item == item:
# 如果cur所指向的节点的元素item与要删除的item元素一致
if not pre:
# pre 如果还是None 说明是头结点
# pre = None
# print(not pre) # True
self._head = cur.next#当前cur指向第一个节点
# cur.next为原链表的第二个节点
else:
#cur为要删除的节点，但不是头结点
'''pre为cur的前一个节点,cur为要删除的节点
使用cur节点的后一个节点的左连线连接删除节点的前一个元素的右连线'''
pre.next = cur.next
else:#当cur指向的节点所包含的item元素不是要寻找的item时
pre = cur
cur = cur.next #继续向下寻找
def search(self,item):
'''查看链表中是否存在item元素,通过遍历进行查找'''
cur = self._head #指向头结点
while cur != None:#当cur指向的不为空时
if cur.item == item:#当找到该元素时
return True
cur = cur.next#在while循环内部，不断进行遍历
return False
单向循环链表
'''
is_empty() 链表是否为空
length() 查询链表长度
travel() 遍历整个链表,到头节点结束
add(item) 链表头部添加元素(头节点作为下一个节点，最后一个节点为node节点)
append(item) 链表尾部添加元素,头节点为node的下一个节点
insert(pos,item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在
'''
class Node(object):
"""节点"""
def __init__(self, item):
self.item = item
self.next = None
class SinCycLinkedlist(object):
"""单向循环链表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head == None
def length(self):
"""返回链表的长度"""
# 如果链表为空，返回长度0
if self.is_empty():
return 0
count = 1
cur = self._head
while cur.next != self._head:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历链表"""
if self.is_empty():
return
cur = self._head
print (cur.item,)
while cur.next != self._head:
cur = cur.next
print(cur.item,)
print ("")
def add(self, item):
"""头部添加节点"""
node = Node(item)
if self.is_empty():
self._head = node
node.next = self._head
else:
#添加的节点指向_head
node.next = self._head
# 移到链表尾部，将尾部节点的next指向node
cur = self._head
while cur.next != self._head:
cur = cur.next
cur.next = node
#_head指向添加node的
self._head = node
def append(self, item):
"""尾部添加节点"""
node = Node(item)
if self.is_empty():
self._head = node
node.next = self._head
else:
# 移到链表尾部
cur = self._head
while cur.next != self._head:
cur = cur.next
# 将尾节点指向node
cur.next = node
# 将node指向头节点_head
node.next = self._head
def insert(self, pos, item):
"""在指定位置添加节点"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
cur = self._head
count = 0
# 移动到指定位置的前一个位置
while count < (pos-1):
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def remove(self, item):
"""删除一个节点"""
# 若链表为空，则直接返回
if self.is_empty():
return
# 将cur指向头节点
cur = self._head
pre = None
# 若头节点的元素就是要查找的元素item
if cur.item == item:
# 如果链表不止一个节点
if cur.next != self._head:
# 先找到尾节点，将尾节点的next指向第二个节点
while cur.next != self._head:
cur = cur.next
# cur指向了尾节点
cur.next = self._head.next
self._head = self._head.next
else:
# 链表只有一个节点
self._head = None
else:
pre = self._head
# 第一个节点不是要删除的
while cur.next != self._head:
# 找到了要删除的元素
if cur.item == item:
# 删除
pre.next = cur.next
return
else:
pre = cur
cur = cur.next
# cur 指向尾节点
if cur.item == item:
# 尾部删除
pre.next = cur.next
def search(self, item):
"""查找节点是否存在"""
if self.is_empty():
return False
cur = self._head
if cur.item == item:
return True
while cur.next != self._head:
cur = cur.next
if cur.item == item:
return True
return False
双向链表
'''
is_empty() 链表是否为空
length() 查询链表长度
travel() 遍历整个链表
add(item) 链表头部添加元素
append(item) 链表尾部添加元素
insert(pos,item) 指定位置添加元素
remove(item) 删除节点
search(item) 查找节点是否存在
'''
class Node(object):
"""双向链表节点"""
def __init__(self, item):
self.item = item
self.next = None
self.pre = None
class DLinkList(object):
"""双向链表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head == None
def length(self):
"""返回链表的长度"""
cur = self._head
count = 0
while cur != None:
count += 1
cur = cur.next
return count
def travel(self):
"""遍历链表"""
cur = self._head
while cur != None:
print(cur.item,)
cur = cur.next
print(" ")
def add(self, item):
"""头部插入元素"""
node = Node(item)
if self.is_empty():
# 如果是空链表，将_head指向node
self._head = node
else:
# 将node的next指向_head的头节点
node.next = self._head
# 将_head的头节点的pre指向node
self._head.pre = node
# 将_head 指向node
self._head = node
def append(self, item):
"""尾部插入元素"""
node = Node(item)
if self.is_empty():
# 如果是空链表，将_head指向node
self._head = node
else:
# 移动到链表尾部
cur = self._head
while cur.next != None:
cur = cur.next
# 将尾节点cur的next指向node(先左后右)
cur.next = node
# 将node的pre指向cur
node.pre = cur
def search(self, item):
"""查找元素是否存在"""
cur = self._head
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False
def insert(self, pos, item):
"""在指定位置添加节点"""
if pos <= 0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
cur = self._head
count = 0
# 移动到指定位置的前一个位置
while count < (pos-1):
count += 1
cur = cur.next
# 将node的pre指向cur(node左右,cur右左)
node.pre = cur
# 将node的next指向cur的下一个节点
node.next = cur.next
# 将cur的下一个节点的pre指向node
cur.next.pre = node
# 将cur的next指向node
cur.next = node
def remove(self, item):
"""删除元素"""
if self.is_empty():
return
else:
cur = self._head
if cur.item == item:
# 如果首节点的元素即是要删除的元素
if cur.next == None:
# 如果链表只有这一个节点
self._head = None
else:
# 将第二个节点的pre设置为None
cur.next.pre = None
# 将_head指向第二个节点
self._head = cur.next
return
while cur != None:
if cur.item == item:
# 将cur的前一个节点的next指向cur的后一个节点
cur.pre.next = cur.next
# 将cur的后一个节点的pre指向cur的前一个节点
cur.next.pre = cur.pre
break
cur = cur.next
2020-05-07