Soul Searching: Why Data structures?
Data structures, in plain English, are the study of how data is stored. Data storage has only one purpose, that is, to facilitate the later reuse of data. Therefore, the storage of data in computer storage space is not random, which requires us to choose a good way to store data, and this is the core content of data structure. It can be said that data structures are fundamental to all programming. Learning data structures is learning the idea of how to translate real problems into computer language representations. For computer learning friends, learning data structure is a basic skill. For non computer major, but in the future to data analysis, development direction of large data, or on the use of Python can be the friend that has a large span, the data structure is a kind of very important logical thinking ability of exercise, in employment, career development, problem solving, etc, can have subtle big help.
Tips: This article is just a guide for you to learn. If you encounter any problems during the learning process, be sure to search related blogs, articles, books and other materials as supplementary learning. Without further ado, let’s turn it on! @TOC
1. Linear table (linear storage structure)
Linear tables are the simplest data storage structures among data structures and can be understood as “linear tables”. Linearity means that the data has a linear relationship in logical structure. Data with one-to-one relationship is stored linearly in physical space. This storage structure is called linear storage structure (linear table for short).
1.1 Basic introduction to linear tables
Linear tables, the simplest type of storage structure for data structures, are designed to store data with a one-to-one logical relationship. Based on the storage state of data in the actual physical space, it can be subdivided into sequential list (sequential storage structure) and linked list (chain storage structure).
Linear table, full name for linear storage structure. The way to store data in linear tables is to “string all the data together on a string and store it in physical space”.
As shown in Figure 1, this is a set of data with a one-to-one relationship, which we then store in physical space using linear tables.
First, use a “string” to “string” them in order, as shown in Figure 2:
In Figure 2, data is “strung” on the left and free physical space is on the right. To place this “bundle” of data into physical space, we can choose one of two ways, as shown in Figure 3.
Figure 3a) is the way most people think of storage, while Figure 3B) is less popular. We know that the success of data storage depends on restoring data to its original form. If you pull up one end of the lines in Figures 3a and 3b, you will see that the data position remains unchanged (as in Figure 1). Therefore, it can be concluded that both storage methods are correct.
Data that has a one-to-one relationship is stored “linearly” in physical space **. This storage structure is called linear storage structure (linear table).
Data stored in linear tables, like data stored in arrays, must be of the same type, that is, all data stored in linear tables must be either integers or strings. A set of data that is half an integer and half a string cannot be stored using a linear table.
1.2 Sequential storage and chain storage
In Figure 3, we can see that the data stored in linear tables can be divided into the following two types:
(1) As shown in FIG. 3A, data is sequentially stored in the whole contiguous physical space. This storage structure is called sequential storage structure (sequence table for short);
(2) As shown in FIG. 3B), data are distributed in physical space and the logical relationship between them is preserved through a line. This storage structure is called chained storage structure (linked list for short).
In other words, linear table storage structure can be subdivided into sequential storage structure and chain storage structure.
1.3 Predecessors and Successors
In data structures, each individual in a set of data is called a “data element” (an “element” for short). For example, Figure 1 shows the set of data where 1, 2, 3, 4, and 5 are all elements in the set.
In addition, for data with one-to-one logic, we have been using untechnical terms like “left (front) or right (back) of an element”, but there are more accurate terms in the linear table:
The adjacent elements to the left of an element are called “direct precursors”, and all elements to the left of this element are collectively called “precursors”.
The adjacent elements to the right of an element are called “immediate successors”, and all elements to the right of this element are collectively called “successors”.
For element 3 in figure 1, its direct precursor is 2. There are two precursor elements of this element, 1 and 2 respectively. Similarly, the immediate successor of this element is 4, and there are two subsequent elements, 4 and 5. As shown below:
2. Sequential table (sequential storage structure)
2.1 Sequence Table Basic introduction
A sequential table, full name sequential storage structure, is a type of linear table. Through the learning of “What is a linear table” section, we know that a linear table is used to store data with a logical relationship of “one to one”, and the sequential table is no exception.
Not only that, sequential tables also have requirements on the physical storage structure of data. To store data in a sequential table, a physical space of sufficient size is applied for in advance and data is stored sequentially, ensuring that there is no gap between data elements.
For example, if a sequential table is used to store the collection {1,2,3,4,5}, the final storage state of the data is shown in Figure 1:
Therefore, we can conclude that the storage structure that “has’ one to one ‘logical relation data is sequentially stored in a whole physical space” is the sequential storage structure.
By looking at the storage state of the data in Figure 1, we can see that a sequential table stores data very similar to an array. In fact, sequential tables store data using arrays.
2.2 Insert elements for basic operation of sequence table
Insert data elements into the existing sequence table, according to the different insertion position, can be divided into the following three situations: ① Insert data elements into the table head of the sequence table; Insert element in middle of table; ③ Follow the existing element in the order list as the last element in the order list;
Although the insertion sequence of data elements in the table is different, but the use of the same way to solve, that is: through traversal, find the data element to insert the position, and then do the following two steps: (1) to insert the position of the element and the subsequent element overall move back one position; ② Place the element in the position vacated;
For example, insert element 6 in the third position of {1,2,3,4,5} as follows:
① Traverse to the location where the third data element is stored in the sequence table, as shown in Figure 1:
② Move element 3 and subsequent elements 4 and 5 back one position as a whole, as shown in Figure 2:
③ Put the new element 6 into the vacated position, as shown in Figure 3:
2.3 Delete elements for basic operation of sequence table
Removing a specified element from a sequence table is as simple as finding the target element and advancing all its subsequent elements by one place.
[Note] : If the subsequent element moves forward by one position, the target element will be deleted directly, which can indirectly achieve the purpose of deleting the element.
For example, the process for removing element 3 from {1,2,3,4,5} is shown in figure 4:
2.4 Search elements for basic operations in the sequence table
To find the target element in the order list, we can use a variety of search algorithms, such as binary search algorithm, interpolation search algorithm and so on.
2.5 Change elements for the basic operation of the sequence table
The sequence table changes the elements by: (1) find the target element; (2) Directly modify the value of the element; About the sequence table Python programming implementation code can refer to ↓ (personal writing, only for reference, welcome to put forward valuable suggestions)
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2021/7/20 15:42
# @Author : vaxtiandao
# @File : ds_1.py
import random
random.seed(10)
Define the order table class
class SqList() :
# initialization
def __init__(self, length) :
self.length = length First specify the length of the array
self.sqlist = [random.randint(1.100) for j in range(length)] # Generate a random number set of length
Output all elements
def ShowList(self) :
return self.sqlist
Walk through all elements
def ErgodicList(self) :
for i in range(self.length):
print("{} th element is {}".format(i+1, self.sqlist[i]))
# values
def GetElem(self, i) :
Insert position (1,length)
if i < 1 or i > self.length:
pass
return False
return self.sqlist[i-1] If # is present, return the value directly
# to find
def LocateElem(self, e) :
# Loop through the list to find the element equal to e and return its position index
for j in range(self.length):
if e == self.sqlist[j]:
return j
break
Otherwise, print "The element searched does not exist in the list" and return False
print("No element found in the list.")
# insert
def ListInsert(self, i, e) :
Insert position (1,length) within the legal range
if i < 1 or i > self.length:
return False
return self.sqlist.insert(i,e) # Insert () is in the list
# remove
def ListDelete(self, i) :
Insert position (1,length) within the legal range
if i < 1 or i > self.length:
return False
return self.sqlist.pop(i) The # list has a pop() function that returns the deleted value
Define a sequence table object
length = 10
my_sqlist = SqList(length)
print("Initialization sequence table:", my_sqlist)
print("_________________________________________________")
Print all parameters
mylist = my_sqlist.ShowList()
print("Output all parameters:", mylist)
print("_________________________________________________")
Call the traversal function
print("Traversal order table")
my_sqlist.ErgodicList()
print("_________________________________________________")
# insert
print("List before insertion: {}".format(my_sqlist.ShowList()))
i = 4 Insert index position
e = 10 # Insert value
my_sqlist.ListInsert(i, e) Insert the value at the specified index position
print("Insert order table: {}".format(my_sqlist.ShowList()))
print("_________________________________________________")
# remove
i = 5 Delete index position
print("Order table before deletion: {}".format(my_sqlist.ShowList()))
my_sqlist.ListDelete(i) # drop the value of index I
print("Deleted order table: {}".format(my_sqlist.ShowList()))
print("_________________________________________________")
# values
index = 8 # represents the 10th number, not the number with the position index of 10.
value = my_sqlist.GetElem(index)
if value:
print("The number {} in the sequence is equal to {}".format(index, value))
print("_________________________________________________")
# to find
e = 55 # the number to find
index = my_sqlist.LocateElem(e)
if index:
print("Element {} has an index of {} in the order table.".format(e, index))
Copy the codeHere is the result:
3. Single linked list, chain storage structure
3.1 Basic introduction to single linked lists
In this section, we introduce another linear storage structure, linked lists.
A linked list, also known as a chained storage structure or singly linked list, is used to store data that has a “one to one” logical relationship. Unlike sequential lists, linked lists do not limit the physical storage state of data; in other words, the physical storage location of data elements stored in linked lists is random.
For example, using a linked list to store {1,2,3}, the physical storage state of the data is shown in Figure 1:
As we can see, the diagram does not show the logical relationship between the data at all. The solution to this is that each data element is stored with a pointer to its immediate successor. As shown in Figure 2:
As shown in Figure 2, a storage structure in which data elements are stored randomly and logical relationships between data are represented by Pointers is a chained storage structure.
3.2 Nodes of a linked list
As can be seen from the figure above, the storage of each data in the linked list is composed of the following two parts: (1) The data element itself, which is called the data domain; (2) The region where the pointer points to the direct successor element is called the pointer field;
That is, the structure of each data element stored in the linked list is shown in Figure 3:
The structures shown above are called nodes in linked lists. That is, linked lists actually store nodes one by one, and the real data elements are contained in these nodes, as shown in Figure 4:
3.3 Head nodes, head Pointers, and head primitives
In fact, the linked list structure shown in Figure 4 is not complete. A complete linked list should consist of the following parts:
1. Header pointer: a normal pointer that always points to the first node in the list. Obviously, the header pointer is used to indicate the location of the linked list so that it can be found and used later.
2. Node: The nodes in the linked list are subdivided into head node, head node and other nodes: (1) Head node: in fact, an empty node without any data, usually as the first node of the linked list. For linked lists, the head node is not necessary, it is only for the convenience of solving some practical problems; (2) Primary node: Due to the head node (i.e., empty node), the first node with data is called the primary node in the linked list. The header node is just a name for the first data node in the linked list, which has no practical significance. (3) Other nodes: other nodes in the linked list;
Thus, a complete linked list structure that stores {1,2,3} is shown in figure 5:
[Note] : When there is a head node in the linked list, the head pointer points to the head node; Otherwise, if there is no head node in the list, the head pointer points to the head node.
Now that you understand the basic structure of a linked list, let’s learn how to create one.
3.4 Creating a Linked List (initialization)
To create a linked list, do the following:
1. Declare a header pointer (or a header node if necessary);
2. When creating multiple nodes to store data, establish logical relationships with their predecessors at any time.
3.5 Basic operations of single linked lists
This section details some of the basic operations on linked lists, including adding, deleting, finding (traversing), and changing data in linked lists.
Insert elements
Like the sequential list, adding elements to the linked list can be divided into the following three situations according to the different positions of adding elements: (1) Insert elements to the head of the linked list (after the head node) as the first node; (2) Insert it somewhere in the middle of the list; (3) Insert into the end of the linked list as the last data element in the list;
Although the insertion position of the new element is not fixed, but the idea of the linked list insertion element is fixed, just do the following two steps to insert the new element to the specified position: (1) The next pointer of the new node points to the node after the insertion position; (2) Set the next pointer of the node before the insertion position to the insertion node;
For example, on the basis of linked list {1,2,3,4}, new element 5 is inserted in the head, middle and tail respectively, as shown in Figure 1:
As can be seen from the figure, although the insertion positions of new elements are different, the insertion operations are implemented in the same way: step 1 is performed first, and then Step 2.
[Note] : The operation of linked list insert element must be first step 1, then step 2; On the contrary, if step 2 is performed first, unless another pointer is added as the head pointer of the subsequent linked list at the insertion position, this part of the linked list after the insertion position will be lost and step 1 cannot be realized
Remove elements
When you remove a specified data element from a linked list, you are actually removing the node containing the data element from the list. However, as a qualified programmer, you should be responsible for the storage space and timely release the storage space that is no longer used. Therefore, deleting data elements from the linked list requires the following 2 steps: (1) Remove nodes from the linked list; (2) Manually release the node and reclaim the storage space occupied by the node;
The implementation of removing a node from the list is as simple as finding the immediate precursor of the node, temp. For example, if we remove element 3 from the list with {1,2,3,4}, this code will look like figure 2:
Look for the element
The most common method to find a specified data element in a linked list is to traverse the nodes in the table in turn from the table header and compare the searched element with the data element stored in the data field of each node until the comparison succeeds or the NULL (the symbol of the failure of the comparison) is traversed to the end of the linked list.
Note that when traversing the linked list with head nodes, it is necessary to avoid the impact of head nodes on test data. Therefore, when traversing the linked list, the traversal method in the above code is established to effectively traverse the linked list directly over the head nodes.
Update the element
To update an element in a linked list, simply traverse the node where the element is stored and make changes to the data fields in the node. The Python code for linked list programming can be found in the ↓ (personally written for reference only, welcome to give valuable suggestions).
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2021/7/21 17:12
# @Author : vaxtiandao
# @File : ds_12.py
# Implementation of one-way linked list
Each node contains two parts, a data area and a link to the next node
# One-way list: Each node contains two parts: the data area and the link area (pointing to the next node), and the link area for the last element is None
All nodes can be accessed as long as the head node is found
A node class contains two members: a node element value and a pointer to the next node
class SingleNode() :
The node class is initialized
def __init__(self, item) :
self.item = item # item stores the value of the node
self.next = None # Next pointer points to
# Define singly linked lists
class SingleLinkList() :
Initialize the linked list class
def __init__(self) :
self.head = None
Check whether the linked list is empty
def is_empty(self) :
return self.head == None
Output list length
def get_length(self) :
return len(self.travel())
Walk through the list
def travel(self) :
Check if the list is empty
# is null and returns None,
If not null, first define a list, then use the next pointer to start from scratch, then add the value stored in the node to the list in turn, until the next pointer is null, then stop traversing;
if self.is_empty():
return None
else:
curlist = []
cur = self.head
whilecur ! =None:
curlist.append(cur.item)
cur = cur.next
return curlist
Create a singly linked list using the header method
def add(self, newItem) :
node = SingleNode(newItem)
node.next = self.head # pointer transform
self.head = node
# tail interpolation
def append(self, newItem) :
node = SingleNode(newItem)
if self.is_empty():
return self.add(newItem)
Start traversal from the beginning
nod = self.head
while nod.next! =None: # stop traversal when next is None
nod = nod.next
nod.next = node
Add the element at the specified location
def insert(self, pos, newItem) : Add the newItem element to the pos position
There are several cases for the insertion of linked lists
# The first step is to determine whether pos is within a reasonable range. If not, it will terminate directly
The second step is to check whether pos is in the first position, if so, use the headplug method
If pos is in the last position, use the tail insertion method
Step 4 if there is neither a header nor a tail, loop through to pos and Insert
node = SingleNode(newItem)
cur = self.head
count = 0
if pos == 0:
return self.add(newItem)
elif pos < (self.get_length()):
while count < pos - 1:
cur = cur.next
count += 1
node.next = cur.next
cur.next = node
elif pos == (self.get_length()):
return self.append(newItem)
else:
return 'Wrong location entered, please confirm'
# delete node at specified position
def remove(self, pos) :
# The first step is to judge whether the given POS is within the reasonable range
The second step is to traverse the pos position through a loop. During the traverse, the next pointer points to the next node in turn
Nod.next = nod.next-next
cur = self.head
count = 0
if 1 <= pos < (self.get_length()):
while count < pos - 1:
cur = cur.next
count += 1
cur.next = cur.next.next
elif pos == 0:
self.head = cur.next
else:
return 'Wrong location entered, please confirm'
Find the value of the node at the specified position
def find(self, pos) :
cur = self.head
count = 0
if 0 <= pos < (self.get_length()):
while count < pos:
cur = cur.next
count += 1
return cur.item
else:
return 'Wrong location entered, please confirm'
Update the value of a location in the linked list
def update(self, pos, newItem) :
cur = self.head
count = 0
if 0 <= pos < (self.get_length()):
while count < pos:
cur = cur.next
count += 1
cur.item = newItem
else:
return 'Wrong location entered, please confirm'
## Clear the linked list
def clear(self) :
self.head = None
singlelinklist = SingleLinkList() Instantiate the object
print("Initialize a single linked list:",singlelinklist)
print("________________________________________________________________________________________________")
print("Determine if a single linked list is empty:",singlelinklist.is_empty())
print("________________________________________________________________________________________________")
# add data
import random
for i in range(10):
singlelinklist.add(random.randint(1.100))
# walk through the data
singlelinklist.travel()
print("Traversing a single linked list:",singlelinklist.travel())
print("________________________________________________________________________________________________")
print("Determine if a single linked list is empty:",singlelinklist.is_empty())
print("________________________________________________________________________________________________")
Add data at the end
singlelinklist.append(10)
print("Result of traversal of a single linked list after adding elements to the end:", singlelinklist.travel())
print("________________________________________________________________________________________________")
# Add data at the beginning
singlelinklist.add(1)
print("Result of single linked list traversal after adding elements at the beginning:", singlelinklist.travel())
print("________________________________________________________________________________________________")
# Check the data length
print("Single list length:",singlelinklist.get_length())
print("________________________________________________________________________________________________")
Insert data at the specified position, starting at 0
singlelinklist.insert(1.13)
print("Traversal single linked list after insertion:", singlelinklist.travel())
print("________________________________________________________________________________________________")
# delete location data
singlelinklist.remove(0)
print("Traversal single linked list after deleting data:", singlelinklist.travel())
print("________________________________________________________________________________________________")
# update location data
singlelinklist.update(2.2)
print("Traversal single linked list with updated data:", singlelinklist.travel())
print("________________________________________________________________________________________________")
# Delete all data
singlelinklist.clear()
print("Traversal single linked list after clearing data:", singlelinklist.travel())
print("________________________________________________________________________________________________")
Copy the codeHere is the code implementation:
4. One-way circular linked lists
Singly and bidirectionally linked lists are like an alley where you end up going from one end to the other, whereas a circular list is like an alley with a portal, because when you think you’re at the end of a circular list, you’re back at the beginning.
Circular and non-circular lists are created in exactly the same way. The only difference is that the tail of a non-circular list points to NULL, while the tail pointer of a circular list points to the beginning of the list. A list that points the tail of a single linkedlist to the head is called a Circular linkedlist.
As shown in the figure, is a complete circular single linked list;
4.1 Node Design of Circular Linked List (Taking Single Circular Linked List as an example)
For the nodes of the circular single-linked list, the node design of the single-linked list can be completely referred to, as shown in the figure:
Data represents data, which can be a simple type (int,double, etc.) or a complex structure (struct type).
Next is a pointer, which always points to its next node, which always points to itself if only one node exists, and next always points to the beginning of a linked list.
4.2 Initialization of a circular Singly linked list
Like create a singly linked list, we need to first create a head node and to create a memory space, but unlike singly linked list, we need to open the memory space after successful head node of the next point to the head itself, we can create an init function to finish the thing, repeat in the future to create and insert, We can consider that next points to null after init is recreated, and that the next pointer to the head points to itself after the main function call is created.
This way of operation can facilitate the creation of a single linked list, directly using the insertion function called many times to complete the creation of the whole.
4.3 Basic operations of circular singly linked lists
The basic operations of a circular single linked list include: initialization, nulling, traversal, create (head/tail), output length, add, delete, find, update, and empty; The Python code for linked list programming can be found in the ↓ (personally written for reference only, welcome to give valuable suggestions).
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2021/7/21 17:16
# @Author : vaxtiandao
# @File : ds_13.py
A node class contains two members: a node element value and a pointer to the next node
class SingleNode() :
The node class is initialized
def __init__(self, item) :
self.item = item # store the value of the node
self.next = None # Next pointer points to
# Define singly linked lists
class SingleLinkList() :
Initialize the linked list class
def __init__(self, node=None) :
self.head = node # point to the header
if node:
node.next = node If a node is entered when instantiating an object, define a node loop
Check whether the linked list is empty
def is_empty(self) :
return self.head == None
Output list length
def get_length(self) :
if self.is_empty():
return 0
cur = self.head
count = 1
while cur.next! = self.head: count +=1
cur = cur.next
return count
Walk through the list
def travel(self) :
curlist = []
if self.is_empty():
return curlist
cur = self.head
while cur.next! = self.head: curlist.append(cur.item) cur = cur.next
curlist.append(cur.item)
return curlist
Create a singly linked list using the header method
def add(self, newItem) :
node = SingleNode(newItem)
cur = self.head
if self.head is None:
self.head = node
node.next = node
else:
while cur.next! = self.head: cur = cur.next
node.next = self.head
self.head = node
cur.next = node
Create a singly linked list
def append(self, newItem) :
node = SingleNode(newItem)
Start traversal at the end of the node
cur = self.head
if self.is_empty():
self.head = node
node.next = node
else:
while cur.next! = self.head: cur = cur.next
node.next = self.head
cur.next = node
Add elements at the specified location,pos starts from zero
def insert(self, pos, newItem) :
node = SingleNode(newItem)
if pos <= 0:
self.add(newItem)
elif pos > (self.get_length() - 1):
self.append(newItem)
else:
count = 0
cur = self.head
while count < (pos - 1):
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
# delete node at specified position
def remove(self, pos) :
if pos <= 0:
return 'Data is empty'
elif pos > (self.get_length() - 1) :return 'Beyond list range'
else:
count = 0
cur = self.head
while count < (pos - 1):
count += 1
cur = cur.next
cur.next = cur.next.next
Find the value of the node at the specified position
def find(self, pos) :
if pos <= 0:
return 'Data is empty'
elif pos > (self.get_length() - 1) :return 'Beyond list range'
else:
count = 0
cur = self.head
while count < pos:
count += 1
cur = cur.next
return cur.item
Update the value of a location in the linked list
def update(self, pos, newItem) :
if pos <= 0:
return 'Data is empty'
elif pos > (self.get_length() - 1) :return 'Beyond list range'
else:
count = 0
cur = self.head
while count < pos:
count += 1
cur = cur.next
cur.item = newItem
# Clear the linked list
def clear(self) :
self.head = None
Instantiate the object
import random
singlelinklist = SingleLinkList()
print("Initialize object:", singlelinklist)
print("________________________________________________________________________________________________")
Check if the linked list is empty
print(After initialization, determine whether the current linked list is empty:, singlelinklist.is_empty())
print("________________________________________________________________________________________________")
Add data randomly
for i in range(10):
singlelinklist.add(random.randint(1.100))
Check if the linked list is empty
print("Determine if the current linked list is empty:", singlelinklist.is_empty())
print("________________________________________________________________________________________________")
View linked list data
print("Iterate through the list to see the list elements:", singlelinklist.travel())
print("________________________________________________________________________________________________")
Query the length of the linked list
print("The current list length is", singlelinklist.get_length())
print("________________________________________________________________________________________________")
# interpolation
print("Iterate through the list to see the linked list elements before inserting:", singlelinklist.travel())
singlelinklist.add(0)
print("After the header is inserted, traverse the list to see the linked list elements:", singlelinklist.travel())
print("________________________________________________________________________________________________")
# tail interpolation
print("Walk through the list to see the list elements before inserting:", singlelinklist.travel())
singlelinklist.append(100)
print("After insertion, traverse the list to see the list elements:", singlelinklist.travel())
print("________________________________________________________________________________________________")
Insert values at the specified location
print("Traverses the list to see linked list elements before inserting at specified location:", singlelinklist.travel())
singlelinklist.insert(3.3)
print("After inserting at the specified location, traverse the list to see the list elements:", singlelinklist.travel())
print("________________________________________________________________________________________________")
Find the value of the node at the specified position
print("Find node value at specified position:", singlelinklist.find(5))
print("________________________________________________________________________________________________")
# delete the value of the specified position
print("Traverse the list to see the linked list elements before deleting:", singlelinklist.travel())
singlelinklist.remove(6)
print("After deletion, traverse the list to see the linked list elements:", singlelinklist.travel())
print("________________________________________________________________________________________________")
# update the value of the specified location
print("Iterate through the list to see the list elements before updating:", singlelinklist.travel())
singlelinklist.update(3.15)
print("After update, traverse the list to see the list elements:", singlelinklist.travel())
print("________________________________________________________________________________________________")
# empty node
print("Clean, iterate through the list to see the list elements:", singlelinklist.travel())
singlelinklist.clear()
print("After emptying, traverse the list to see the list elements:", singlelinklist.travel())
print("________________________________________________________________________________________________")
Copy the codeHere’s what the code looks like:
For basic operations on circular single-linked lists, see this 👉 : Basic operations on circular single-linked lists
5. Bidirectional linked lists
5.1 Basic introduction to bidirectional linked lists
All the linked lists we have learned so far, whether dynamic or static, contain only one pointer (cursor) in each node of the list, which uniformly points to the direct successor node. This kind of linked list is usually called one-way linked list (or single linked list).
Although singly linked lists can be used 100% to solve the “one to one” data storage problem, they are not the most efficient storage structure for some special problems. For example, in a scenario where there is a large number of nodes that need to be looked up, single-linked lists can be disastrous, because single-linked lists are better for looking back, not back to front.
For reverse lookup (from back to front) related problems, use the bidirectional linked list explained in this section, will get more results with less effort.
Double linked list, short for double linked list. Bidirectional lists are “bidirectional” by name, as shown in Figure 1:
The so-called bidirectional means that the logical relationship between nodes is bidirectional, but usually only one head pointer can be set. Unless the actual situation requires, another “head pointer” can be set for the last node.
According to Figure 1, each node in the bidirectional linked list contains the following three parts of information (as shown in the figure below) : (1) Pointer field: the direct precursor node used to point to the current node; (2) Data domain: used to store data elements; (3) Pointer field: used to point to the immediate successor of the current node.
5.2 Creation of bidirectional linked lists
Compared to a single linked list, a double linked list simply has one more pointer field for each node to point to a direct precursor. Therefore, we can easily create double-linked lists on the basis of single-linked lists.
(1) Set the prior pointer of the new node to the direct precursor node. (2) set the prior pointer of the new node to the direct precursor node. (2) Set the next pointer of the direct precursor node to the new node;
5.3 Basic operations of bidirectional linked lists
After learning how to create a bidirectional list, this section covers the basics of adding, deleting, finding, or changing data elements to a bidirectional list.
On the basis of having mastered the creation process of bidirectional linked list, we continue to learn the content of this section by continuing the bidirectional linked list created in the previous section, as shown in Figure 1:
Add nodes to a bidirectional list
According to the location of the data added to the bidirectional list, it can be subdivided into the following three situations: (1) Add to table header Add a new data element to the table header, only need to establish a double-layer logical relationship between the element and the table header element. Temp ->next=head; temp->next=head; The head – > the prior = temp; Change head to temp and point to the new table header.
For example, adding a new element 7 to the head of a double-linked list would look like figure 2:
(2) Adding data to the middle of a list is similar to adding data to a single linked list. Adding data to the middle of a bidirectional linked list requires the following two steps, as shown in Figure 3: ① The new node first establishes a two-layer logical relationship with its direct successor node; (2) The direct precursor node of the new node establishes a bi-level logical relationship with it;
(3) Add to the end of the table is the same as add to the head of the table, the implementation process is as follows (as shown in Figure 4) : ① Find the last node in the double-linked list; (2) Let the new node and the last node to carry out a two-layer logic relationship;
Bidirectionally linked lists remove nodes
To delete a node from a double-linked list, you simply traverse the list to find the node to delete, and then remove it from the table.
For example, the procedure for deleting element 2 from Figure 1 is shown in Figure 5:
Bidirectional linked lists find nodes
In general, a bidirectional list, like a single list, has only one header pointer. Therefore, the implementation of a double-linked list to find a specified element is similar to that of a single-linked list, in that the elements are traversed from the table head.
Bidirectional linked lists change nodes
Changes to the data fields of a specified node in a double-linked list are done on a look-up basis. The implementation process is: by traversing to find the node where the data element is stored, directly change its data field can be. The Python code for linked list programming can be found in the ↓ (personally written for reference only, welcome to give valuable suggestions).
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# @Time : 2021/7/22 9:14
# @Author : vaxtiandao
# @File : ds_14.py
A node class contains two members: a node element value and a pointer to the next node
class SingleNode() :
The node class is initialized
def __init__(self, item) :
self.item = item # store the value of the node
self.next = None # Next pointer points to
self.hail = None The previous pointer points to
# Define singly linked lists
class DoubleLinkList() :
Initialize the linked list class
def __init__(self) :
self.head = None # point to the header
self.hail = None # point to the endpoint
Check whether the linked list is empty
def is_empty(self) :
return self.head == None
Output list length
def get_length(self) :
return len(self.travel())
Walk through the list
def travel(self) :
curlist = []
cur = self.head
whilecur ! =None:
curlist.append(cur.item)
cur = cur.next
return curlist
Create a singly linked list using the header method
def add(self, newItem) :
node = SingleNode(newItem)
if self.head is not None:
node.next = self.head
self.head = node
node.next.prev = node
else:
self.head = node
self.hail = node
Create a singly linked list
Def append(self,newItem): node = SingleNode(newItem) self.head = node while cur.next ! = None: cur = cur.next cur.next = node node.prev = cur'''
def append(self, newItem) :
node = SingleNode(newItem)
if self.hail is not None:
self.hail.next = node
node.prev = self.hail
self.hail = node
else:
self.hail = node
self.head = node
Add elements at the specified location,pos starts from zero
def insert(self, pos, newItem) :
node = SingleNode(newItem)
if pos <= 0:
self.add(newItem)
elif pos > (self.get_length() - 1):
self.append(newItem)
else:
count = 0
cur = self.head
while count < pos:
count += 1
cur = cur.next
node.next = cur
node.prev = cur.prev
cur.prev.next = node
cur.prev = node
# delete node at specified position
def remove(self, pos) :
cur = self.head
count = 0
if 1 <= pos < (self.get_length()):
while count < pos - 1:
cur = cur.next
count += 1
cur.next = cur.next.next
cur.next.prev = cur
elif pos == 0:
self.head = cur.next
else:
return 'Wrong location entered, please confirm'
Find the value of the node at the specified position
def find(self, pos) :
cur = self.head
count = 0
if 0 <= pos < (self.get_length()):
while count < pos:
cur = cur.next
count += 1
return cur.item
else:
return 'Wrong location entered, please confirm'
Update the value of a location in the linked list
def update(self, pos, newItem) :
cur = self.head
count = 0
if 0 <= pos < (self.get_length()):
while count < pos:
cur = cur.next
count += 1
cur.item = newItem
else:
return 'Wrong location entered, please confirm'
# Clear the linked list
def clear(self) :
self.head = None
self.hail = None
Instantiate the object
doublelinklist = DoubleLinkList()
print("Initializing a bidirectional list:", doublelinklist)
print("________________________________________________________________________________________________")
Check if the linked list is empty
print("List is empty until element is inserted:", doublelinklist.is_empty(), end="")
print("________________________________________________________________________________________________")
Add data randomly using header interpolation
import random
for i in range(10):
doublelinklist.add(random.randint(1.100))
Check whether the linked list is empty
print("The list is not empty after inserting elements:", doublelinklist.is_empty())
print("________________________________________________________________________________________________")
Select * from list length
print("The current list length is:", doublelinklist.get_length())
print("________________________________________________________________________________________________")
# view data
print("The current bidirectional list traversal element is:", doublelinklist.travel())
print("________________________________________________________________________________________________")
Use tail-insertions
print("Before the tail insertion method, the element after the bidirectional list traversal is:", doublelinklist.travel())
doublelinklist.append(10)
print("After tail insertion, the element after bidirectional list traversal is:", doublelinklist.travel())
print("________________________________________________________________________________________________")
# Use the headplug method
print("Before the head insertion method, the element after the bidirectional list traversal is:", doublelinklist.travel())
doublelinklist.add(0)
print("After head insertion, the elements of the bidirectional list traversal are:", doublelinklist.travel())
print("________________________________________________________________________________________________")
Insert values at the specified location
print("Before inserting at the specified position, the element after the bidirectional list traversal is:", doublelinklist.travel())
doublelinklist.insert(1.1)
print("After insertion at the specified position, the element after bidirectional list traversal is:", doublelinklist.travel())
print("________________________________________________________________________________________________")
# find the value at the specified location
t = 5
print("The current value of the {} element is:".format(t), doublelinklist.find(t))
print("________________________________________________________________________________________________")
# delete the value of the specified position
print("Before deleting the value of the specified position, the element after the bidirectional list traversal is:", doublelinklist.travel())
doublelinklist.remove(4)
print("Before deleting the value of the specified position, the element after the bidirectional list traversal is:", doublelinklist.travel())
print("________________________________________________________________________________________________")
# update the value of the specified location
doublelinklist.update(5.5)
print("The current bidirectional list traversal element is:", doublelinklist.travel())
print("________________________________________________________________________________________________")
Clear list data
doublelinklist.clear()
print("The current bidirectional list traversal element is:", doublelinklist.travel())
print("________________________________________________________________________________________________")
Copy the codeThe following is the effect of the above code: