单向链表
#!usr/bin/env python
# -*- coding:utf-8 -*-
"""
@author:yzk13
@time: 2018/04/15
单向链表
"""
class Node(object):
"""
节点类
"""
def __init__(self, value, next):
self.value = value
# 下一个节点
self.next = next
class LinkedList(object):
"""
链表
"""
def __init__(self):
self.root = None
def addNode(self, value):
"""
添加Node
:return:
"""
if self.root == None:
self.root = Node(value=value, next=None)
return self.root
else:
# 有头节点,需要遍历到链表尾部,然后添加节点
cursor = self.root
while cursor.next != None:
cursor = cursor.next
cursor.next = Node(value=value, next=None)
return self.root
def append(self, value):
"""
在尾部添加Node
:return:
"""
self.addNode(value)
def prepend(self, value):
"""
在表头添加Node
:param value:
:return:
"""
if self.root == None:
self.addNode(value)
else:
newNode = Node(value, self.root)
self.root = newNode
@property
def length(self):
"""
获取链表长度
:return:
"""
counter = 0
if self.root == None:
counter = 0
return counter
else:
cursor = self.root
while cursor != None:
counter += 1
cursor = cursor.next
return counter
def insert(self, index, value):
"""
在index处插入Node
:param index:
:param value:
:return:
"""
if self.root == None:
return None
if index < 0 or index > self.length - 1:
print('Index 非法,超出索引')
elif index == 0:
# 表头
self.prepend(value)
elif index == self.length - 1:
# 表尾
self.append(value)
else:
# 使用计数器来确定位置
counter = 1
pre = self.root
cursor = self.root.next
while cursor != None:
if counter == index:
tmp = Node(value, Node)
pre.next = tmp
tmp.next = cursor
break
else:
counter += 1
pre = cursor
cursor = cursor.next
def delNode(self, index):
"""
删除Node
:param index:
:return:
"""
if self.root == Node:
return None
if index < 0 or index > self.length - 1:
print('Index 非法,超出索引')
elif index == 0:
self.root = self.root.next
else:
pre = self.root
cursor = pre.next
counter = 1
while cursor != None:
if index == counter:
pre.next = cursor.next
break
else:
pre = cursor
cursor = cursor.next
counter += 1
def print(self):
"""
打印链表
:return:
"""
if self.root == None:
print('Nothing')
return None
else:
cursor = self.root
# 开头的[
print('[', end='')
while cursor != None:
# 输出结尾的]
if cursor.next == None:
print(cursor.value, end=']')
cursor = None
else:
print(cursor.value, end=', ')
cursor = cursor.next
print()
def delValue(self, value):
"""
删除值为value的Node
:param value:
:return:
"""
if self.root == None:
return None
if self.root.value == value:
self.root = self.root.next
else:
pre = self.root
cursor = pre.next
while cursor != None:
if cursor.value == value:
pre.next = cursor.next
cursor = cursor.next
continue
else:
pre = cursor
cursor = cursor.next
def is_empty(self):
"""
判断链表是否为空
:return:
"""
if self.root == None or self.length == 0:
return True
else:
return False
def getValue(self, index):
"""
获取指定位置的节点值
:param index:
:return:
"""
if self.root == None:
return None
if index < 0 or index > self.length - 1:
print('Index 非法,超出索引')
elif index == 0:
return self.root.value
else:
counter = 0
cursor = self.root
while cursor != None:
if counter == index:
return cursor.value
else:
counter += 1
cursor = cursor.next
def getValueIndex(self, value):
"""
获取值为某个值的索引
:return:
"""
indexs = []
if self.root == None:
return None
if self.root.value == value:
self.root = self.root.next
indexs.append(0)
else:
index = 1
cursor = self.root
while cursor != None:
if cursor.value == value:
indexs.append(index)
index += 1
cursor = cursor.next
return indexs
def peek(self):
"""
获取尾部节点,且不删除该节点
:return:
"""
return self.getValue(self.length - 1)
def pop(self):
"""
获取表尾节点并删除
:return:
"""
if self.root == None or self.length == 0:
print('空表')
return None
if self.length == 1:
top = self.root.value
self.root = None
return top
else:
pre = self.root
cursor = pre.next
while cursor.next != None:
pre = cursor
cursor = cursor.next
top = cursor.value
cursor = None
pre.next = None
return top
def updateNode(self, index, value):
"""
修改指定位置的节点
:param index:
:return:
"""
if self.root == None:
return None
if index < 0 or index > self.length - 1:
print('Index 非法, 索引不在范围内')
if index == 0:
self.root.value = value
else:
cursor = self.root.next
counter = 1
while cursor != None:
if counter == index:
cursor.value = value
break
cursor = cursor.next
counter += 1
def delDuplecate(self):
"""
删除重复的元素 ????????????
:return:
"""
# 使用一个map来存放即可,类似于变形的“桶排序”
if self.root == None:
return None
if self.length == 1:
return None
pre = self.root
cursor = pre.next
dic = {}
# 为字典赋值
temp = self.root
while temp != None:
dic[str(temp.value)] = 0
temp = temp.next
temp = None
# 开始实施删除重复元素的操作
while cursor != None:
if dic[str(cursor.value)] == 1:
pre.next = cursor.next
cursor = cursor.next
else:
dic[str(cursor.value)] += 1
pre = cursor
cursor = cursor.next
def reverse(self):
"""
逆序 ?????????????????????????????
:return:
"""
if self.root == None:
return None
if self.length == 1:
return None
else:
post = None
pre = None
cursor = self.root
while cursor != None:
post = cursor.next
cursor.next = pre
pre = cursor
cursor = post
self.root = pre
def delLinkedList(self):
"""
删除链表
:return:
"""
if self.root == None:
return None
else:
self.root = None
def getNode(self, index):
if self.root == None:
return None
if index == 0:
return self.root
if index < 0 or index > self.length:
print('Index 非法, 索引不在范围内')
else:
counter = 0
cursor = self.root
while cursor != None:
if counter == index:
return cursor
cursor = cursor.next
counter += 1
if __name__ == '__main__':
# ------创建链表-------
linkedlist = LinkedList()
# ------添加节点-------
linkedlist.addNode(1)
linkedlist.prepend(0)
linkedlist.insert(0, -1)
linkedlist.insert(2, -3)
linkedlist.print()
# ------测试插入节点-------
linkedlist.insert(1, 6)
linkedlist.print()
# ------测试删除节点-------
linkedlist.delNode(3)
linkedlist.print()
linkedlist.addNode(0)
linkedlist.print()
# ------测试删除某值的节点-------
linkedlist.delValue(0)
linkedlist.print()
# ------测试获取节点的值-------
i = 1
value = linkedlist.getValue(i)
print(i, '处的值为: ', value)
# ------测试查找某值的索引-------
linkedlist.prepend(0)
linkedlist.addNode(1)
linkedlist.addNode(6)
linkedlist.addNode(-3)
linkedlist.print()
print(linkedlist.getValueIndex(-3))
# ------测试获取最后一个值-------
linkedlist.print()
value = linkedlist.peek()
print('链表最后一个值为: ', value)
# ------测试获取并删除最后一个值-------
value = linkedlist.pop()
print('链表最后一个值为: ', value)
linkedlist.print()
# ------测试反转-------
linkedlist.reverse()
print('反转后: ', end='')
linkedlist.print()
# ------测试修改-------
linkedlist.print()
linkedlist.updateNode(5, 7)
print('修改后: ', end='')
linkedlist.print()
# ------测试删除重复-------
# linkedlist.print()
# linkedlist.delDuplecate()
# linkedlist.print()
# -----获取节点-------
node1 = linkedlist.getNode(1)
linkedlist.print()
print(node1.next.value)
# ------清空链表-------
linkedlist.delLinkedList()
linkedlist.print()
# ------测试长度-------
print('链表长度: ', linkedlist.length)