Python implements the linked list instance code
- 2020-05-30 20:26:17
- OfStack
Python implements the linked list instance code
preface
Algorithms and data structures are an eternal topic. As a programmer, it is very, very necessary to master the implementation of common data structures.
Realize the listing
Implementing linked lists is essentially language-independent. But flexibility is closely related to the language in which it is implemented. Today, Python is used to implement 1, including the following operations:
['addNode(self, data)']
['append(self, value)']
['prepend(self, value)']
['insert(self, index, value)']
['delNode(self, index)']
['delValue(self, value)']
['isempty(self)']
['truncate(self)']
['getvalue(self, index)']
['peek(self)']
['pop(self)']
['reverse(self)']
['delDuplecate(self)']
['updateNode(self, index, value)']
['size(self)']
['print(self)']
Generating such a list of methods must not be done manually, otherwise it would be too much trouble, so I wrote a program to match the methods implemented by myself. The code is relatively simple, and the core idea is to match every line of the source file, find the content that matches the matching rules, and add it to the total result set.
The code is as follows:
# coding: utf8
# @Author: guo brand
# @File: getmethods.py
# @Time: 2017/4/5
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: To obtain 1 A list of all methods and parameters in a module or class
import re
def parse(filepath, repattern):
with open(filepath, 'rb') as f:
lines = f.readlines()
# Preanalytic regularity
rep = re.compile(repattern)
# Creates a list of result sets to save the list of methods and parameters
result = []
# Start the formal matching implementation
for line in lines:
res = re.findall(rep, str(line))
print("{} The matching result of {}".format(str(line), res))
if len(res)!=0 or res is not None:
result.append(res)
else:
continue
return [item for item in result if item !=[]]
if __name__ == '__main__':
repattern = "def (.[^_0-9]+\(.*?\)):"
filepath = './SingleChain.py'
result = parse(filepath, repattern)
for item in result:
print(str(item))
Linked list implementation
# coding: utf8
# @Author: guo brand
# @File: SingleChain.py
# @Time: 2017/4/5
# @Contact: 1064319632@qq.com
# @blog: http://blog.csdn.net/marksinoberg
# @Description: Single linked list implementation
class Node(object):
def __init__(self, data, next):
self.data = data
self.next = next
class LianBiao(object):
def __init__(self):
self.root = None
# Add element nodes to a single linked list
def addNode(self, data):
if self.root==None:
self.root = Node(data=data, next=None)
return self.root
else:
# If there is a header node, you need to traverse to the tail node to add to the list
cursor = self.root
while cursor.next!= None:
cursor = cursor.next
cursor.next = Node(data=data, next=None)
return self.root
# Add a new node to the end of the list and the underlying call addNode Methods can be
def append(self, value):
self.addNode(data=value)
# Add a node to the top of the list
def prepend(self, value):
if self.root == None:
self.root = Node(value, None)
else:
newroot = Node(value, None)
# update root The index
newroot.next = self.root
self.root = newroot
# Adds a node to the list at the specified location
def insert(self, index, value):
if self.root == None:
return
if index<=0 or index >self.size():
print('index %d Illegal, Should look at 1 Place your insert node on the entire list! ')
return
elif index==1:
# if index==1 . Then add at the top of the list
self.prepend(value)
elif index == self.size()+1:
# if index It's just longer than the current list 1 , can be added in the tail
self.append(value)
else:
# In this way, add a new node in the middle of the list and add it directly. You need to use counters to maintain insert unknowns
counter = 2
pre = self.root
cursor = self.root.next
while cursor!=None:
if counter == index:
temp = Node(value, None)
pre.next = temp
temp.next = cursor
break
else:
counter += 1
pre = cursor
cursor = cursor.next
# Deletes a node at the specified location
def delNode(self, index):
if self.root == None:
return
if index<=0 or index > self.size():
return
# For the first 1 Three positions need to be handled with care
if index == 1:
self.root = self.root.next
else:
pre = self.root
cursor = pre.next
counter = 2
while cursor!= None:
if index == counter:
print('can be here!')
pre.next = cursor.next
break
else:
pre = cursor
cursor = cursor.next
counter += 1
# Delete a value of value List node elements
def delValue(self, value):
if self.root == None:
return
# For the first 1 Three positions need to be handled with care
if self.root.data == value:
self.root = self.root.next
else:
pre = self.root
cursor = pre.next
while cursor!=None:
if cursor.data == value:
pre.next = cursor.next
# Be sure to update this node, otherwise there will be a dead loop...
cursor = cursor.next
continue
else:
pre = cursor
cursor = cursor.next
# Determine if the list is empty
def isempty(self):
if self.root == None or self.size()==0:
return True
else:
return False
# Deletes the list and all its internal elements
def truncate(self):
if self.root == None or self.size()==0:
return
else:
cursor = self.root
while cursor!= None:
cursor.data = None
cursor = cursor.next
self.root = None
cursor = None
# Gets the value of the node at the specified location
def getvalue(self, index):
if self.root is None or self.size()==0:
print(' Current list is empty! ')
return None
if index<=0 or index>self.size():
print("index %d Illegal! "%index)
return None
else:
counter = 1
cursor = self.root
while cursor is not None:
if index == counter:
return cursor.data
else:
counter += 1
cursor = cursor.next
# Gets the value of the end of the list without deleting the end node
def peek(self):
return self.getvalue(self.size())
# Gets the value of the tail node of the list and deletes it
def pop(self):
if self.root is None or self.size()==0:
print(' The current list is empty! ')
return None
elif self.size()==1:
top = self.root.data
self.root = None
return top
else:
pre = self.root
cursor = pre.next
while cursor.next is not None:
pre = cursor
cursor = cursor.next
top = cursor.data
cursor = None
pre.next = None
return top
# Single linked list reverse implementation
def reverse(self):
if self.root is None:
return
if self.size()==1:
return
else:
# post = None
pre = None
cursor = self.root
while cursor is not None:
# print(' Reverse order operation ')
post = cursor.next
cursor.next = pre
pre = cursor
cursor = post
# Don't forget to assign a value to the head node after the reverse order root , otherwise it cannot be displayed correctly
self.root = pre
# Remove duplicate elements from the list
def delDuplecate(self):
# use 1 a map To store it, sort of like a morphed bucket sort.
dic = {}
if self.root == None:
return
if self.size() == 1:
return
pre = self.root
cursor = pre.next
dic = {}
# Assign a value to the dictionary
temp = self.root
while temp!=None:
dic[str(temp.data)] = 0
temp = temp.next
temp = None
# Start the operation of removing duplicate elements
while cursor!=None:
if dic[str(cursor.data)] == 1:
pre.next = cursor.next
cursor = cursor.next
else:
dic[str(cursor.data)] += 1
pre = cursor
cursor = cursor.next
# Modifies the value of the specified location node
def updateNode(self, index, value):
if self.root == None:
return
if index<0 or index>self.size():
return
if index == 1:
self.root.data = value
return
else:
cursor = self.root.next
counter = 2
while cursor!=None:
if counter == index:
cursor.data = value
break
cursor = cursor.next
counter += 1
# Gets the size of a single linked list
def size(self):
counter = 0
if self.root == None:
return counter
else:
cursor = self.root
while cursor!=None:
counter +=1
cursor = cursor.next
return counter
# Prints the list's own elements
def print(self):
if(self.root==None):
return
else:
cursor = self.root
while cursor!=None:
print(cursor.data, end='\t')
cursor = cursor.next
print()
if __name__ == '__main__':
# create 1 Two linked list objects
lianbiao = LianBiao()
# Determines if the current list is empty
print(" The list is empty %d"%lianbiao.isempty())
# Determines if the current list is empty
lianbiao.addNode(1)
print(" The list is empty %d"%lianbiao.isempty())
# add 1 Some nodes, easy to operate
lianbiao.addNode(2)
lianbiao.addNode(3)
lianbiao.addNode(4)
lianbiao.addNode(6)
lianbiao.addNode(5)
lianbiao.addNode(6)
lianbiao.addNode(7)
lianbiao.addNode(3)
# Prints all the values of the current list
print(' Prints all the values of the current list ')
lianbiao.print()
# Test the linked list size The operation of the
print(" The list of size: "+str(lianbiao.size()))
# Tests the retrieval of the value of the specified location node
print(' Tests the retrieval of the value of the specified location node ')
print(lianbiao.getvalue(1))
print(lianbiao.getvalue(lianbiao.size()))
print(lianbiao.getvalue(7))
# Test to delete the specified value in the linked list, Repeatable deletion
print(' Test to delete the specified value in the linked list, Repeatable deletion ')
lianbiao.delNode(4)
lianbiao.print()
lianbiao.delValue(3)
lianbiao.print()
# Removes duplicate elements from the list
print(' Removes duplicate elements from the list ')
lianbiao.delDuplecate()
lianbiao.print()
# An update test for a linked list element at a specified location
print(' An update test for a linked list element at a specified location ')
lianbiao.updateNode(6, 99)
lianbiao.print()
# Test adding a node to the top of the list
print(' Test adding a node to the top of the list ')
lianbiao.prepend(77)
lianbiao.prepend(108)
lianbiao.print()
# Test adding a node to the end of the list
print(' Test adding a node to the end of the list ')
lianbiao.append(99)
lianbiao.append(100)
lianbiao.print()
# Tests the insert operation of the specified subscript
print(' Tests the insert operation of the specified subscript ')
lianbiao.insert(1, 10010)
lianbiao.insert(3, 333)
lianbiao.insert(lianbiao.size(), 99999)
lianbiao.print()
# test peek operation
print(' test peek operation ')
print(lianbiao.peek())
lianbiao.print()
# test pop operation
print(' test pop operation ')
print(lianbiao.pop())
lianbiao.print()
# Test the reverse output of a single linked list
print(' Test the reverse output of a single linked list ')
lianbiao.reverse()
lianbiao.print()
# Test the linked list truncate operation
print(' Test the linked list truncate operation ')
lianbiao.truncate()
lianbiao.print()
What happens when the code runs? Whether it can meet our needs, please see the printed result:
D:\Software\Python3\python.exe E:/Code/Python/Python3/CommonTest/datastructor/SingleChain.py
The list is empty 1
The list is empty 0
Prints all the values of the current list
1 2 3 4 6 5 6 7 3
The list of size: 9
Tests the retrieval of the value of the specified location node
1
3
6
Test to delete the specified value in the linked list, Repeatable deletion
can be here!
1 2 3 6 5 6 7 3
1 2 6 5 6 7
Removes duplicate elements from the list
1 2 6 5 7
An update test for a linked list element at a specified location
1 2 6 5 7
Test adding a node to the top of the list
108 77 1 2 6 5 7
Test adding a node to the end of the list
108 77 1 2 6 5 7 99 100
Tests the insert operation of the specified subscript
10010 108 333 77 1 2 6 5 7 99 99999 100
test peek operation
100
10010 108 333 77 1 2 6 5 7 99 99999 100
test pop operation
100
10010 108 333 77 1 2 6 5 7 99 99999
Test the reverse output of a single linked list
99999 99 7 5 6 2 1 77 333 108 10010
Test the linked list truncate operation
Process finished with exit code 0
Just met the target requirements.
conclusion
Today's content is still relatively basic, there is no difficulty. But understanding and being able to write are not the same thing, and it's rewarding to write such code when you have nothing to do.