current position:Home>[Python data structure series] linear table - explanation of knowledge points + code implementation

[Python data structure series] linear table - explanation of knowledge points + code implementation

2022-01-30 03:44:13 Vax_ Loves_ one thousand three hundred and fourteen

Soul torture : Why study data structure ?

data structure , Understand directly , It's about studying how data is stored . Data storage has only one purpose , In order to facilitate the later reuse of data . therefore , The storage of data in computer storage space , It's not random , This requires us to choose a good way to store data , And that's the core of data structure . so to speak , Data structure is the basis of all programming . Learning data structures is learning an idea : How to transform the real problem into the representation of computer language . For friends who study computer , Learning data structure is the basic skill . For non computer majors , But in the future, I want to go to data analysis 、 Big data 、 Or in Python For friends who can make a big leap in the use of , Learning data structure is a very important exercise of logical thinking ability , Looking for a job 、 Occupation development 、 Problem solving and other aspects can be of great help .

tips: The knowledge introduced in this article is only used as an introduction , For our friends to learn , If you encounter problems in the process of learning , Be sure to search more related blogs 、 article 、 Books and other materials , As a supplementary study . I don't say much nonsense , Let's drive the whole ! @TOC

1. The linear table ( Linear storage structure )

Linear table is the simplest data storage structure in data structure , It can be understood as “ Linear table ”. linear , It means that the data has a linear relationship in logical structure . Will have “ one-on-one ” The data of the relationship “ linear ” To store in physical space , This kind of storage structure is called linear storage structure ( Linear table for short ).

1.1 Basic introduction to linear table

   The linear table , The simplest storage structure in data structure , Designed to store logical relationships as " one-on-one " The data of . Based on the storage state of data in real physical space , It can also be subdivided into a sequence table ( Sequential storage structure ) And the list ( Chain storage structure ).

   The linear table , Full name Linear storage structure . Using linear tables to store data can be understood in this way , namely " String all the data in one line , And then store it in physical space ".

Image Name

   Pictured 1 Shown , This is a group with “ one-on-one ” The data of the relationship , We then use a linear table to store it in physical space .

   First , use “ A thread ” Put them in order “ strand ” get up , Pictured 2 Shown :

Image Name

   chart 2 in , On the left is “ strand ” Up data , On the right is the free physical space . Put this “ A string of ” Place data in physical space , We can choose the following two ways , Pictured 3 Shown .

Image Name

   chart 3a) It's the way most people think of storage , Diagram 3b) But few people think of . We know , The success of data storage , Depends on whether the data can be completely restored to its original shape . If you take the picture 3a) Sum graph 3b) One end of the line pulled up , You will find that the location of the data has not changed ( Sum graph 1 equally ). Therefore, it can be determined that , Both storage methods are correct .

   Will have **“ one-on-one ” The data of the relationship “ linear ” To store in physical space **, This storage structure is called Linear storage structure ( abbreviation The linear table ).

   Data stored using linear tables , Just like storing data in an array , The data type must be consistent , in other words , Data stored in linear tables , Or it's all plastic surgery , Or it's all strings . Half plastic , The other half is that a set of string data cannot be stored using a linear table .   

1.2 Sequential and chain storage structures

   chart 3 We can see that , Linear table storage data can be subdivided into the following 2 Kind of :

  (1) Pictured 3a) Shown , Store the data in a continuous physical space in turn , This storage structure is called Sequential storage structure ( abbreviation The order sheet );

  (2) Pictured 3b) Shown , The data is scattered in the physical space , The logical relationship between them is preserved through a line , This storage structure is called Chain storage structure ( abbreviation Linked list );

   in other words , Linear table storage structure can be subdivided into sequential storage structure and chain storage structure .

1.3 Forerunner and successor

   data structure in , Each individual in a set of data is called “ data elements ”( abbreviation “ Elements ”). for example , chart 1 This set of data displayed , among 1、2、3、4 and 5 Is an element in this set of data .

   in addition , Those who have “ one-on-one ” Data of logical relationship , We've been using “ The left side of an element ( in front ) Or right ( Back )” Such unprofessional words , In fact, there are more accurate terms in the linear table :

   The left adjacent element of an element is called “ Direct precursor ”, All elements to the left of this element are collectively referred to as “ Precursor elements ”;

   The adjacent elements to the right of an element are called “ Direct follow-up ”, All elements to the right of this element are collectively referred to as “ Subsequent elements ”;

   In an effort to 1 Elements in data 3 Come on , Its immediate precursor is 2 , The precursor elements of this element are 2 individual , Namely 1 and 2; Empathy , The immediate successor to this element is 4 , Subsequent elements also have 2 individual , Namely 4 and 5. As shown in the figure below :

Image Name

2. The order sheet ( Sequential storage structure )

2.1 Basic introduction to sequence table  

   The order sheet , full name Sequential storage structure , It's a kind of linear table . adopt 《 What is a linear table 》 We know that , The linear table is used to store the logical relationship as “ one-on-one ” The data of , The sequence table is no exception .

   More Than This , The order table also requires the physical storage structure of data . When a sequence table stores data , Will apply for a whole piece of physical space of sufficient size in advance , And then store the data one by one , When storing, there is no gap between data elements .

   for example , Use a sequential table to store collections {1,2,3,4,5}, The final storage state of the data is shown in Figure 1 Shown :

Image Name

   From this we can conclude that , take “ have ' one-on-one ' The data of logical relationship is continuously stored on a whole physical space in order ” The storage structure is the sequential storage structure .

   By looking at the picture 1 Storage status of data in , We can find out , A sequential table stores data very close to an array . Actually , Sequential tables store data using arrays .

2.2 Insert element of basic operation of sequence table

  Insert data elements... Into an existing sequence table , Depending on the insertion position , It can be divided into the following 3 In this case :   ① Insert into the header of the sequence table ;   ② Insert elements in the middle of the table ;   ③ There are already elements in the following order table , As the last element in the sequence table ;

  Although the location of the data elements in the insertion order table is different , But they all use the same way to solve , namely : By traversing , Find the location where the data element is to be inserted , Then do the following two steps :   ① Move the position element to be inserted and the subsequent elements as a whole backward one position ;   ② Put the element in the vacated position ;

  for example , stay {1,2,3,4,5} Of the 3 Insert elements... In positions 6, The implementation process is as follows :

  ① Traverse to the sequence table to store the second 3 The location of the first data element , Pictured 1 Shown :

Image Name

  ② Put the element 3 And subsequent elements 4 and 5 Move the whole back one position , Pictured 2 Shown :

Image Name

  ③ The new element 6 Put in the vacated position , Pictured 3 Shown :

Image Name

2.3 Delete element of basic operation of sequence table

   Remove the specified elements from the order table , It's very easy to implement , Just find the target element , And move all subsequent elements forward as a whole 1 Just one place .

  【 notes 】: The following elements move forward one position as a whole , The target element will be deleted directly , The purpose of deleting elements can be achieved indirectly .

   for example , from {1,2,3,4,5} Delete element 3 The process is as shown in the figure 4 Shown :

Image Name

2.4 Search element of basic operation of sequence table

   Find the target element in the sequence table , You can use a variety of search algorithms to achieve , for instance Two points search Algorithm 、 The interpolation to find Algorithm etc. .

2.5 Change element of basic operation of sequence table

   The implementation of the sequence table change element is :   (1) Find the target element ;   (2) Directly modify the value of the element ;    About sequence table Python Programming code can refer to ↓( Personal writing , For reference only , We welcome 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)

#  Class that defines the sequence table 
class SqList():
    #  initialization 
    def __init__(self, length):
        self.length = length  #  Specify the length of the array first 
        self.sqlist = [random.randint(1, 100) for j in range(length)]  #  Generate length A random array of lengths 

    #  Output all elements 
    def ShowList(self):
        return self.sqlist

    #  Traverse all elements 
    def ErgodicList(self):
        for i in range(self.length):
            print(" The first {} The element values are {}".format(i+1, self.sqlist[i]))

    #  Value 
    def GetElem(self, i):
        #  First, judge whether the insertion position is within the legal range (1,length)
        if i < 1 or i > self.length:
            pass
            return False
        return self.sqlist[i-1]  #  If you are , Direct return value 

    #  lookup 
    def LocateElem(self, e):
        #  Loop through the list , Find the list equal to e The elements of , Returns its location index 
        for j in range(self.length):
            if e == self.sqlist[j]:
                return j
                break
        #  otherwise , Output a sentence :" The element you are looking for does not exist in the list ", Then return False
        print(" The element you are looking for does not exist in the list ")

    #  Insert 
    def ListInsert(self, i, e):
        #  First, judge whether the insertion position is within the legal range (1,length), If not , Go straight back to False
        if i < 1 or i > self.length:
            return False
        return self.sqlist.insert(i,e)  #  The list is insert() function 

    #  Delete 
    def ListDelete(self, i):
        #  First, judge whether the insertion position is within the legal range (1,length), If not , Go straight back to False
        if i < 1 or i > self.length:
            return False
        return self.sqlist.pop(i)  #  The list has a pop() function , This function will return the deleted value 

#  Define a sequence table object 
length = 10
my_sqlist = SqList(length)
print(" Initialization sequence table :", my_sqlist)
print("_________________________________________________")
#  Output 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 #  Inserted index position 
e = 10 #  Inserted value 
my_sqlist.ListInsert(i, e)  #  Inserts a value at the specified index position 
print(" The inserted sequence table :{}".format(my_sqlist.ShowList()))
print("_________________________________________________")
#  Delete 
i = 5 #  Index location deleted 
print(" The order table before deletion :{}".format(my_sqlist.ShowList()))
my_sqlist.ListDelete(i)  #  Delete i The value at the location of the index 
print(" Deleted sequence table :{}".format(my_sqlist.ShowList()))
print("_________________________________________________")
#  Value 
index = 8  #  Here stands for the second 10 Number , Not the location index is 10 Number of numbers , Indexes +1 Is the specific number ;
value = my_sqlist.GetElem(index)
if value:
    print(" No.. In the sequence table {} The number is equal to {}".format(index, value))
print("_________________________________________________")
#  lookup 
e = 55  #  Number to find 
index = my_sqlist.LocateElem(e)
if index:
    print(" Elements {} The index in the sequential table is {}".format(e, index))
 Copy code 

Here are the results :  Insert picture description here About the basic operation of sequence table C The language code , You can see this : Basic operation of sequence table

3. Single chain list , Chain storage structure

3.1 Basic introduction to single linked list

   Previously, I introduced in detail The order sheet , This section introduces you to another Linear storage structure —— Linked list .

   Linked list , Alias Chain storage structure or Single chain list , It is used to store the logical relationship as " one-on-one " The data of . Different from the sequence table , The linked list does not limit the physical storage state of data , let me put it another way , Use linked list to store data elements , Its physical storage location is random .

   for example , Using linked list storage {1,2,3}, The physical storage status of the data is shown in the figure 1 Shown :

Image Name

   We see , The above figure can not reflect the logical relationship between the data . Regarding this , The solution to the linked list is , Each data element is stored with a pointer , Used to point to its own direct successor element . Pictured 2 Shown :

Image Name

   Image map 2 such , Data elements are stored randomly , The storage structure that represents the logical relationship between data through pointers is the chain storage structure .

3.2 The nodes of the list

   You can see from the above picture that , The storage of each data in the linked list consists of the following two parts :   (1) The data element itself , The area where it is located is called the data field ;   (2) A pointer to the immediate successor element , The area where the pointer is located is called the pointer field ;

   That is, the structure of each data element stored in the linked list is shown in Figure 3 Shown :

Image Name

   The structure shown in the figure above is called node in the linked list . in other words , The linked list actually stores nodes one by one , The real data elements are contained in these nodes , Pictured 4 Shown :

Image Name

3.3 Head node , Header pointer and first element node

  Actually , chart 4 The linked list structure shown is not complete . A complete linked list needs to be composed of the following parts :

  1. The head pointer : An ordinary pointer , It is characterized by always pointing to the position of the first node in the linked list . Obviously , The header pointer is used to indicate the position of the linked list , It is convenient to find the linked list and use the data in the list later ;

  2. node : The nodes in the linked list are subdivided into head nodes 、 First element node and other nodes :   (1) Head node : In fact, it is an empty node without any data , Usually as the first node of the linked list . For a linked list , The header node is not required , Its function is only to facilitate the solution of some practical problems ;   (2) Primary node : Because the head node ( That is, an empty node ) Why , In the linked list, the first node with data is called the first meta node . The first element node is just an appellation for the first data node in the linked list , No practical significance ;   (3) Other nodes : Other nodes in the linked list ;

  therefore , A store {1,2,3} The complete linked list structure is shown in the figure 5 Shown :

Image Name

 【 notes 】: When there is a header node in the linked list , The head pointer points to the head node ; conversely , If there is no header node in the linked list , Then the header pointer points to the initial node .

  Understand the basic structure of the linked list , Let's learn how to create a linked list .

3.4 Creation of linked list ( initialization )

To create a linked list, you need to do the following :

 1. Declare a header pointer ( If necessary , You can declare a header node );

 2. Create multiple nodes for storing data , In the process of creation , Establish a logical relationship with its predecessor node at any time ;

3.5 Basic operation of Single Chain Watch

   This section will introduce some basic operations of linked list in detail , Including the addition of data in the linked list 、 Delete 、 lookup ( Traverse ) And change .

Insert elements

   Same as the sequence table , Add elements to the list , Depending on the location of the addition , It can be divided into the following 3 In this case :   (1) Insert into the head of the list ( After the head node ), As a primitive node ;   (2) Insert it somewhere in the middle of the list ;   (3) Insert at the end of the list , As the last data element in the linked list ;

   Although the insertion position of the new element is not fixed , But the idea of inserting elements into linked lists is fixed , Just do the following two steps , The new element can be inserted into the specified position :   (1) Will the new node of next The pointer points to the node after the insertion position ;   (2) Will be inserted into the node before the position next The pointer points to the insertion node ;

   for example , We're in the linked list {1,2,3,4} On the basis of the implementation in the head respectively 、 In the middle 、 Insert new elements at the end 5, The implementation process is shown in the figure 1 Shown :

Image Name

   As you can see from the diagram , Although the insertion position of the new element is different , But the way to implement the insert operation is consistent , All steps are performed first 1 , Next step 2.

  【 Be careful 】: The operation of inserting elements into the linked list must be the first step 1, Next step 2; conversely , If you perform step first 2, Unless you add another pointer , As the head pointer of the subsequent linked list at the insertion position , Otherwise, this part of the linked list after the insertion position will be lost , Step... Can no longer be implemented 1

Remove elements

   Delete the specified data element from the linked list , In fact, the node containing the data element is removed from the linked list , But as a qualified programmer , Be responsible for the storage space , Release the unused storage space in time . therefore , To delete a data element from a linked list, you need to do the following 2 Step by step :   (1) Remove the node from the linked list ;   (2) Release node manually , Reclaim the storage space occupied by nodes ;

   among , The implementation of removing a node from a linked list is very simple , Just find the direct precursor node of the node temp, for example , From being {1,2,3,4} Delete the element from the linked list of 3, The execution effect of this code is shown in the figure 2 Shown :

Image Name

Look for the element

   Find the specified data element in the linked list , The most common method is : Traverse the nodes in the table in turn from the header , Compare the searched element with the data element stored in the data field of each node , Until the comparison is successful or the end of the linked list is traversed NULL( Flag of failed comparison ).

   Be careful , When traversing the linked list of header nodes , It is necessary to avoid the impact of header nodes on test data , So when traversing the linked list , Establish and use the traversal method in the above code , Directly go over the node to effectively traverse the linked list .

Update elements

   Update elements in linked list , Just traverse to find the node where this element is stored , Change the data field in the node .    On linked list Python Programming code can refer to ↓( Personal writing , For reference only , We welcome 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 , Data area and link to next node 
#  One way list : Each node contains two parts : Data area and link area ( Point to next node ), The link area of the last element is None
#  One way list, just find the header node , You can access all nodes 

#  Define node class , Contains two members : Node element value and pointer to the next node 
class SingleNode():
    #  Node class initialization 
    def __init__(self, item):
        self.item = item  # item Store the value of the node 
        self.next = None  #  The next pointer points to 


#  Define a single chain table 
class SingleLinkList():
    #  Linked list class initialization 
    def __init__(self):
        self.head = None

    #  Judge whether the list is empty 
    def is_empty(self):
        return self.head == None

    #  Output linked list length 
    def get_length(self):
        return len(self.travel())

    #  Traverse the entire list 
    def travel(self):
        #  The idea is to first judge whether the linked list is empty 
        #  Empty to return directly to None,
        #  Not empty words , Just define a list , And then through next The pointer traverses from the beginning , Add the values stored in the node to the list in turn , Until the next pointer points to null , Then stop traversing ;
        if self.is_empty():
            return None
        else:
            curlist = []
            cur = self.head
            while cur != None:
                curlist.append(cur.item)
                cur = cur.next
            return curlist

    #  Head insertion creates a single chain table 
    def add(self, newItem):
        node = SingleNode(newItem)
        node.next = self.head  #  Pointer transformation 
        self.head = node

    #  The tail interpolation 
    def append(self, newItem):
        node = SingleNode(newItem)
        if self.is_empty():
            return self.add(newItem)
        #  Traverse from the beginning of the node 
        nod = self.head
        while nod.next != None:  #  Of the next node next by None when , Stop traversal //  notes : It's different from the Internet , Try to create a new single linked list by tail interpolation 
            nod = nod.next
        nod.next = node

    #  Add elements at specified locations 
    def insert(self, pos, newItem):  #  In the specified pos Add... To the location newItem Elements 
        #  The insertion of linked list needs to be divided into several situations 
        #  First step   Judge pos Is it within a reasonable range , If not , It will terminate directly 
        #  The second step   Judge pos Whether in the first , If so, use the head insertion method 
        #  The third step   If pos In the last , Tail interpolation method is used 
        #  Step four   If it's not in the head , No more tail , Then loop through to pos Location , Reuse Insert 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 ' The position entered is incorrect , Please make sure the '

    #  Delete the node at the specified location 
    def remove(self, pos):
        #  First step   Judge a given pos Whether it is within a reasonable range 
        #  The second step   Through the loop , Traversing pos Location , Pass during traversal next The pointer points to the next node in turn 
        #  The third step   After finding the node at the specified location , adopt nod.next = nod.next.next Delete 
        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 ' The position entered is incorrect , Please make sure the '

    #  Find the node value at the specified location 
    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 ' The position entered is incorrect , Please make sure the '

    #  Update the value of a position 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 ' The position entered is incorrect , Please make sure the '

    ##  Empty the list 
    def clear(self):
        self.head = None


singlelinklist = SingleLinkList() #  Instantiate objects 
print(" Initialize single chain table :",singlelinklist)
print("________________________________________________________________________________________________")
print(" Determine whether the single chain table is empty :",singlelinklist.is_empty())
print("________________________________________________________________________________________________")
#  Add data 
import random
for i in range(10):
    singlelinklist.add(random.randint(1,100))
#  Traversal data 
singlelinklist.travel()
print(" Traversing a single linked list :",singlelinklist.travel())
print("________________________________________________________________________________________________")
print(" Determine whether the single chain table is empty :",singlelinklist.is_empty())
print("________________________________________________________________________________________________")
#  Add data at the end 
singlelinklist.append(10)
print(" The single linked list traversal result after adding elements at the end :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  Add data at the beginning 
singlelinklist.add(1)
print(" The single linked list traversal result after adding elements at the beginning :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  View data length 
print(" Single list length :",singlelinklist.get_length())
print("________________________________________________________________________________________________")
#  Insert data at specified location , Location slave 0 Start 
singlelinklist.insert(1, 13)
print(" Traverse the single linked list after inserting data :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  Delete specified location data 
singlelinklist.remove(0)
print(" Traversal single linked list after deleting data :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  Update the specified location data 
singlelinklist.update(2,2)
print(" Traversal single linked list after updating data :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  Clear all data 
singlelinklist.clear()
print(" Traverse the single linked list after clearing the data :", singlelinklist.travel())
print("________________________________________________________________________________________________")
 Copy code 

The following is the code implementation effect :  Insert picture description here The basic operation of single linked list is detailed C The language code , See here : Basic operation of single chain table

4. One way circular list

For single linked list and two-way linked list , It's like an alley , In any case, you can finally go from one end to the other , However, the circular linked list is like an alley with a portal , Because of the circular list, when you think you're at the end , In fact, you are back to the beginning .

   In fact, the process and idea of creating circular linked list and non circular linked list are almost the same , The only difference is , The tail node of acyclic linked list points to null (NULL), The tail pointer of the circular linked list points to the beginning of the linked list . By pointing the tail node of the single linked list to the head node, the linked list is called circular single linked list (Circular linkedlist)

   Pictured , For a complete circular single linked list ;

1562924138210258.png

4.1 Circular linked list node design ( Take the single cycle linked list as an example )

   For the nodes of circular single linked list , It can completely refer to the node design of single linked list , Pictured :

1562924163903311.png

  data According to the data , It can be a simple type ( Such as int,double wait ), It can also be a complex structure (struct type );

  next Said a pointer , It always points to its next node , For the existence of only one node , This next The pointer always points to itself , For the tail node of a linked list ,next Always point to the beginning .

4.2 Loop single linked list initialization

   Like the creation of a single linked list , We need to create a header node and open up memory space for it , But unlike a single linked list , After the memory space is successfully opened, we need to delete the header node next Point to head Oneself , We can create one init Function to do this , For future repetitions, create and insert , We can consider in init Recreated node next Pointing empty , After the main function call is created, you can manually say head The first node next The pointer points to itself .

   This operation method can facilitate the creation of single linked list in the future , The overall creation can be completed by directly using the multiple call insertion function .

4.3 The basic operation of circular single linked list

   The basic operations of circular single linked list include : initialization 、 Sentenced to empty 、 Traverse 、 establish ( Head insertion / Tail insertion )、 Output length 、 add to 、 Delete 、 lookup 、 Update and empty ;    On linked list Python Programming code can refer to ↓( Personal writing , For reference only , We welcome valuable suggestions )

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/21 17:16 
# @Author : vaxtiandao
# @File : ds_13.py

#  Define node class , Contains two members : Node element value and pointer to the next node 
class SingleNode():
    #  Node class initialization 
    def __init__(self, item):
        self.item = item  #  Store the value of the node 
        self.next = None  #  The next pointer points to 


#  Define a single chain table 
class SingleLinkList():
    #  Linked list class initialization 
    def __init__(self, node=None):
        self.head = node  #  Point to the head node 
        if node:
            node.next = node  #  If the node is entered when instantiating the object , Define node loops 

    #  Judge whether the list is empty 
    def is_empty(self):
        return self.head == None

    #  Output linked 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

    #  Traverse the entire 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

    #  Head insertion creates a single chain table 
    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 single chain table by tailing 
    def append(self, newItem):
        node = SingleNode(newItem)
        #  Starting from the tail 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 specified locations ,pos Starting from scratch 
    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 the node at the specified location 
    def remove(self, pos):
        if pos <= 0:
            return ' Data is empty '
        elif pos > (self.get_length() - 1):
            return ' Beyond the range of linked list '
        else:
            count = 0
            cur = self.head
            while count < (pos - 1):
                count += 1
                cur = cur.next
            cur.next = cur.next.next

    #  Find the node value at the specified location 
    def find(self, pos):
        if pos <= 0:
            return ' Data is empty '
        elif pos > (self.get_length() - 1):
            return ' Beyond the range of linked list '
        else:
            count = 0
            cur = self.head
            while count < pos:
                count += 1
                cur = cur.next
            return cur.item

    #  Update the value of a position in the linked list 
    def update(self, pos, newItem):
        if pos <= 0:
            return ' Data is empty '
        elif pos > (self.get_length() - 1):
            return ' Beyond the range of linked list '
        else:
            count = 0
            cur = self.head
            while count < pos:
                count += 1
                cur = cur.next
            cur.item = newItem

    #  Empty the list 
    def clear(self):
        self.head = None


#  Instantiate objects 
import random

singlelinklist = SingleLinkList()
print(" Initialize object :", singlelinklist)
print("________________________________________________________________________________________________")
#  Check whether the linked list is empty 
print(" After the initialization , Determine whether the current list is empty :", singlelinklist.is_empty())
print("________________________________________________________________________________________________")
#  Add data randomly 
for i in range(10):
    singlelinklist.add(random.randint(1, 100))
#  Check whether the linked list is empty 
print(" Determine whether the current list is empty :", singlelinklist.is_empty())
print("________________________________________________________________________________________________")
#  View linked list data 
print(" Traverse the linked list to view the linked list elements :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  The length of the query list 
print(" The current chain length is ", singlelinklist.get_length())
print("________________________________________________________________________________________________")
#  The first interpolation 
print(" Before inserting the head , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
singlelinklist.add(0)
print(" After the head is inserted , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  The tail interpolation 
print(" Before tail insertion , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
singlelinklist.append(100)
print(" After tail insertion , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  Insert the value... At the specified location 
print(" Before inserting at the specified position , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
singlelinklist.insert(3, 3)
print(" After insertion at the specified position , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  Find the node value at the specified location 
print(" Find the node value at the specified location :", singlelinklist.find(5))
print("________________________________________________________________________________________________")
#  Delete the value at the specified location 
print(" Before deleting , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
singlelinklist.remove(6)
print(" After deleting , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  Update the value of the specified location 
print(" Before updating , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
singlelinklist.update(3, 15)
print(" After the update , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
print("________________________________________________________________________________________________")
#  Empty nodes 
print(" Before emptying , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
singlelinklist.clear()
print(" After emptying , Traverse the linked list to view the linked list elements :", singlelinklist.travel())
print("________________________________________________________________________________________________")
 Copy code 

The following is the implementation effect of the above code :  Insert picture description here

   About the basic operation of circular single linked list , See here : The basic operation of circular single linked list

5. Double linked list

5.1 Basic introduction to two-way linked list

   What we have learned so far Linked list , Whether it's a dynamic linked list or a static linked list , Each node in the table contains only one pointer ( The cursor ), And they all point to the direct successor nodes , This kind of linked list is usually called One way linked list ( or Single chain list ).

   Although using a single linked list can 100% Solve the logical relationship as " one-on-one " Data storage problem , But when solving some special problems , Single linked list is not the most efficient storage structure . for instance , In a scene, it is necessary to find a large number of forward nodes of a node , In this case, using a single linked list is undoubtedly disastrous , Because a single linked list is more suitable for " Before and after " look for ," From back to front " Finding is not its strength .

   For reverse lookup ( From back to front ) Related issues , Use the two-way linked list explained in this section , It will get twice the result with half the effort .

   Double linked list , abbreviation Double linked list . Understand two-way linked list from name , That is, the linked list is " two-way " Of , Pictured 1 Shown :

Image Name

   The so-called two-way , It means that the logical relationship between nodes is bidirectional , But usually the header pointer is set to only one , Unless the actual situation requires , You can set another... For the last node “ The head pointer ”.

   According to the figure 1 It's not hard to see. , Each node in the bidirectional linked list contains the following 3 Some information ( As shown in the figure below ):   (1) Pointer to the domain : Used to point to the direct predecessor node of the current node ;   (2) Data fields : Used to store data elements ;   (3) Pointer to the domain : Used to point to the immediate successor of the current node .

Image Name

5.2 Creation of double linked list

   Compared with a single linked list , A double linked list is just a pointer field for each node to point to the direct precursor . therefore , We can easily realize the creation of double linked list on the basis of single linked list .

   Different from creating a single linked list , In the process of creating a two-way linked list , Each new node must establish two links with the predecessor node , Namely :   (1) Change the prior The pointer points to the direct precursor node ;   (2) Will be the direct precursor node of next Pointer to new node ;

5.3 Basic operation of two-way linked list

   I learned how to create a two-way linked list , In this section, learn about some basic operations of two-way linked list , That is, how to add 、 Delete 、 Find or change data elements .

   This section of knowledge is based on having mastered the creation process of two-way linked list , Let's continue the two-way linked list created in the previous section to learn the content of this section , Create a good two-way linked list, as shown in the figure 1 Shown :

Image Name

Add nodes to the bidirectional linked list

   According to the location of the data added to the bidirectional linked list , It can be subdivided into the following 3 In this case :        (1) Add to header    Add a new data element to the header , You just need to establish a two-level logical relationship between the element and the header element .    let me put it another way , Suppose the new element node is temp, The header node is head, You need to do the following 2 Step by step :    ① temp->next=head; head->prior=temp;    ② take head Moved to temp, Re point to the new header ;

   for example , The new element 7 Add to header of double linked list , The implementation process is shown in Figure 2 Shown :

Image Name

   (2) Add to the middle of the table    Similar to adding data to a single linked list , Adding data in the middle of the bidirectional linked list needs to go through the following 2 A step , Pictured 3 Shown :    ① The new node first establishes a two-level logical relationship with its immediate successor ;    ② The direct precursor node of the new node establishes a two-layer logical relationship with it ;

Image Name

  (3) Add to the tail    It is the same as adding to the header , The implementation process is as follows ( Pictured 4 Shown ):    ① Find the last node in the double linked list ;    ② Let the new node and the last node have a two-level logical relationship ;

Image Name

Double linked list delete node

   When double linked list delete node , Just traverse the linked list to find the node to be deleted , Then remove the node from the table .

   for example , From the picture 1 Delete elements based on 2 The operation process is shown in the figure 5 Shown :

Image Name

Two way linked list lookup node

   Usually , Double linked list is the same as single linked list , They all have only one head pointer . therefore , The implementation of double linked list to find the specified element is similar to that of single linked list , All of them traverse the elements in the table from the header in turn .

Two way linked list change node

   The operation of changing the specified node data field in the double linked list is completed on the basis of searching . The implementation process is : Find the node where the data element is stored by traversing , Change its data field directly .    On linked list Python Programming code can refer to ↓( Personal writing , For reference only , We welcome valuable suggestions )

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
# @Time : 2021/7/22 9:14 
# @Author : vaxtiandao
# @File : ds_14.py
#  Define node class , Contains two members : Node element value and pointer to the next node 
class SingleNode():
    #  Node class initialization 
    def __init__(self, item):
        self.item = item  #  Store the value of the node 
        self.next = None  #  The next pointer points to 
        self.hail = None  #  The previous pointer points to 


#  Define a single chain table 
class DoubleLinkList():
    #  Linked list class initialization 
    def __init__(self):
        self.head = None  #  Point to the head node 
        self.hail = None  #  Point to the tail node 

    #  Judge whether the list is empty 
    def is_empty(self):
        return self.head == None

    #  Output linked list length 
    def get_length(self):
        return len(self.travel())

    #  Traverse the entire list 
    def travel(self):
        curlist = []
        cur = self.head
        while cur != None:
            curlist.append(cur.item)
            cur = cur.next
        return curlist

    #  Head insertion creates a single chain table 
    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 single chain table by tailing 
    '''def append(self,newItem): node = SingleNode(newItem) #  Starting from the tail node  cur = self.head if self.is_empty(): 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 specified locations ,pos Starting from scratch 
    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 the node at the specified location 
    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 ' The position entered is incorrect , Please make sure the '

    #  Find the node value at the specified location 
    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 ' The position entered is incorrect , Please make sure the '

    #  Update the value of a position 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 ' The position entered is incorrect , Please make sure the '

    #  Empty the list 
    def clear(self):
        self.head = None
        self.hail = None


#  Instantiate objects 
doublelinklist = DoubleLinkList()
print(" Initializing a double linked list :", doublelinklist)
print("________________________________________________________________________________________________")
#  Check if the list is empty 
print(" The linked list is empty before the element is inserted :", doublelinklist.is_empty(), end="")
print("________________________________________________________________________________________________")
#  Add data randomly using head interpolation 
import random
for i in range(10):
    doublelinklist.add(random.randint(1, 100))
#  Judge whether the list is empty 
print(" After inserting the element, the linked list is not empty :", doublelinklist.is_empty())
print("________________________________________________________________________________________________")
#  Query linked list length 
print(" The current chain length is :", doublelinklist.get_length())
print("________________________________________________________________________________________________")
#  View the data 
print(" After traversing the current two-way linked list, the element is :", doublelinklist.travel())
print("________________________________________________________________________________________________")
#  Use tail insertion 
print(" Before tail interpolation , After traversing the two-way linked list, the element is :", doublelinklist.travel())
doublelinklist.append(10)
print(" After tail interpolation , After traversing the two-way linked list, the element is :", doublelinklist.travel())
print("________________________________________________________________________________________________")
#  Use head insertion 
print(" Before head insertion , After traversing the two-way linked list, the element is :", doublelinklist.travel())
doublelinklist.add(0)
print(" After head insertion , After traversing the two-way linked list, the element is :", doublelinklist.travel())
print("________________________________________________________________________________________________")
#  Insert the value... At the specified location 
print(" Before inserting at the specified position , After traversing the two-way linked list, the element is :", doublelinklist.travel())
doublelinklist.insert(1, 1)
print(" After the specified position is inserted , After traversing the two-way linked list, the element is :", doublelinklist.travel())
print("________________________________________________________________________________________________")
#  Find the value at the specified location 
t = 5
print(" The current linked list is no {}  The number of elements is :".format(t), doublelinklist.find(t))
print("________________________________________________________________________________________________")
#  Delete the value at the specified location 
print(" Before deleting the specified location value , After traversing the two-way linked list, the element is :", doublelinklist.travel())
doublelinklist.remove(4)
print(" Before deleting the specified location value , After traversing the two-way linked list, the element is :", doublelinklist.travel())
print("________________________________________________________________________________________________")
#  Update the value of the specified location 
doublelinklist.update(5, 5)
print(" After traversing the current two-way linked list, the element is :", doublelinklist.travel())
print("________________________________________________________________________________________________")
#  Clear linked list data 
doublelinklist.clear()
print(" After traversing the current two-way linked list, the element is :", doublelinklist.travel())
print("________________________________________________________________________________________________")


 Copy code 

The following is the implementation effect of the above code :  Insert picture description here    About the basic operation of two-way linked list C The language code , See here : Basic operation of double linked list

copyright notice
author[Vax_ Loves_ one thousand three hundred and fourteen],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201300344110079.html

Random recommended