1 Single linked list concept
- Singly linked list is a data structure of chain access, which stores the data elements in a linear table with a set of arbitrary storage units.
- The data in the linked list is represented by nodes. The composition of each node is: element (image of data elements) + pointer (indicating the storage location of subsequent elements). The element is the storage unit of data, and the pointer is the address data connecting each node.
Here is a single linked list of leading nodes:
- A linear table with a chain storage structure will use an arbitrary set of storage locations to store the data elements in the linear table.
- Because do not need in order to store, lists the insert, delete, faster than sequential storage when data elements, but in finding a node will be slower than stored in order, use the chain store can overcome order linear table need to know in advance the disadvantage of data size, chain table structure can make full use of memory space, realize flexible dynamic memory management. But chain storage loses the characteristic of random access of array and increases the pointer field of node.
2 Single linked list implementation
2.1 Defining nodes
Create the values of the two attributes that the node has, the element element and the pointer next
# Create single linked list node
class Node:
def __init__(self, element) :
self.element = element # Define the element of the node
self.next = None # Initialize node pointing
Copy the code2.2 Defining a single Linked List (Single Linked List header)
When you create a singlelinked list, you actually create a singlelinked list header (note that the header has only one attribute, next, unlike a node that stores an element), and you add new nodes by pointing to next.
# singly linked list
class SingleLinkList:
# initialization
def __init__(self) :
self.next = None # Initialize header pointing
Copy the code2.3 Implementation of Basic functions
The basic functions are implemented in roughly the same way:
- When the retrieval operation is performed, it relies on the next pointer of the head node to iterate backwards.
- When adding, deleting and modifying operations are performed, the next pointer of the node to be operated is disconnected, pointing to other nodes, and the chain structure is always maintained.
Here, insert node is used as an example:
Inserting a node is essentially taking the next pointer of the previous node to the new node, and then the next pointer of the new node to the next node:
Here is some basic functionality to implement the code:
# singly linked list
class SingleLinkList:
# initialization
def __init__(self) :
self.next = None # Initialize header pointing
Check whether the list is empty
def is_empty(self) :
return self.next= =None
# Determine the length of the list
def length(self) :
cur = self.next # will cur pointed to the first node
len = 0 # count
whilecur ! =None: # Traverse all nodes
len+ =1 # count
cur = cur.next # cur points to the next node
return len
Print list elements and store them in the list
def traverse(self) :
cur = self.next # will cur pointed to the first node
list = [] # Create an empty list
whilecur ! =None: # Traverse all nodes
list.append(cur.element) # Fill the list with elements
cur = cur.next # cur points to the next node
return list
# Add elements to the list header
def add(self, element) :
node = Node(element) # Instantiate the node
node.next = self.next Point the new node to the next of the original header
self.next = node # Point the header to the new node
# Add an element to the end of the list
def append(self, element) :
node = Node(element) # Instantiate the node
if self.is_empty(): Check whether the list is empty
self.next = node If null, point the header to the new node
else:
cur = self.next # point cur to next in the original header
while cur.next! =None: # Traverse all nodes until the last node
cur = cur.next
cur.next = node # point cur to the new node
Adds an element to the list at the specified location
def insert(self, idx, element) :
if idx == 0: When idx=0, call add()
self.add(element)
elif idx == self.length(): Call append() when idx=length
self.append(element)
elif 0 < idx < self.length():
node = Node(element) # Instantiate the node
cur = self.next # point cur to next in the original header
for _ in range(idx-1) :# Find the position where you want to insert the element
cur = cur.next
node.next = cur.next # point the new node to the next element in cur
cur.next = node # point cur to the new node
else:
print("The idX entered is invalid")
# Return node elements by index (index starting from 0)
def find(self, idx) :
if self.is_empty(): Check whether the list is empty
print("The list is empty.")
cur = self.next # point cur to next in the original header
if idx == 0:
return cur.element # returns the current element directly
elif 0 < idx < self.length():
for _ in range(idx-1):
cur = cur.next
return cur.next.element # Returns the element at the specified position
else:
print("The idX entered is invalid")
Delete nodes by index (index starting from 0)
def remove(self, idx) :
if self.is_empty(): Check whether the list is empty
print("The list is empty.")
cur = self.next # point cur to next in the original header
if idx == 0: # Remove the first element
self.next = self.next.next
elif 0 < idx < self.length(): # Delete the element at the specified location
for _ in range(idx-1):
cur = cur.next
cur.next = cur.next.next # cur points directly to the next element
else:
print("The idX entered is invalid")
# Modify node elements by index (index starting from 0)
def update(self, idx, element) :
if self.is_empty(): Check whether the list is empty
print("The list is empty.")
cur = self.next
if idx == 0:
cur.element = element # Modify the first element
elif 0 < idx < self.length():
for _ in range(idx-1):
cur = cur.next
cur.next.element = element # Modify the element at the specified location
else:
print("The idX entered is invalid")
# Check whether the node element exists
def is_exist(self, element) :
cur = self.next
whilecur ! =None: # Traverse all nodes
if cur.element == element: Return true if it exists
return True
cur = cur.next
return False
Copy the code3 Instance Operations
# Create a single linked list
ll = SingleLinkList()
# Add element to header
ll.add(2)
ll.add(5)
ll.add(4)
# Add an element to the end
ll.append(10)
ll.append(34)
ll.append(50)
Insert elements (by index)
ll.insert(1.99)
Delete elements (by index)
ll.remove(1)
Update elements (by index)
ll.update(3.88)
View the list as a list
ll.traverse()
Copy the code# Output results
[4.5.2.88.34.50]
Copy the code