1 introduction

  • Singly linked list is a data structure of chain access, which stores the data elements in a linear table with a set of arbitrary storage units.
  • Some knowledge of singly linked lists is required to write code. Here is the basic functionality of Singly linked lists implemented in Python.
  • Merge sort is used in the code to sort a single linked list. You can refer to here: Python implements merge sort for ordered tables.

2 Create a single linked list

For convenience, operate directly on a single linked list with no head node, as follows:

# Create node
class Node:
    def __init__(self,element) :
        self.element = element
        self.next = None
Copy the code

To facilitate the creation of singly linked lists later, prepare some necessary functions in advance:

# Create a linked list based on the input list
def single_link(list) :
    for count,value in enumerate(list) :if count == 0:                     Insert the first element
            head = Node(value)
            cur = head
        else:                              # Insertion of subsequent elements
            cur.next = Node(value)
            cur = cur.next
    return head

View the list as a list
def traverse(node) :              
        list = []                      
        whilenode ! =None:               # Traverse all nodes
            list.append(node.element)     # Node elements to fill in the list
            node = node.next             
        return list

# Calculate the length of the list
def length(node) :
    cur = node              
    len = 0                 # count
    whilecur ! =None:      # Traverse all nodes
        len+ =1            # count
        cur = cur.next      # cur points to the next node
    return len   
Copy the code

Test the functionality

# Create linked list
a = single_link([99.1.34.2.6.1.35.657.5.3.8.7])

# Check the list length
length(a)
> 12

# View the list (rendered as a list)
traverse(a) 
> [99.1.34.2.6.1.35.657.5.3.8.7]
Copy the code

3 Single linked list inversion

3.1 Recursive inversion

Take a 3-node linked list as an example to sort out the idea:

  • In the process of passing:

Recursion is simple, using the next pointer to the next element every time until there is only one node (recursive exit condition)

  • In the process of returning:
  1. Let’s look at procedure 1, because we only have one node, so we don’t need to do anything.
  2. In procedure 2, to complete the list reversal, we first need to point the head node node2.next. Next to Node2, so that node3 successfully points to Node2. Next is then pointed to null and the list is reversed.
  3. The idea of process 3 is the same as the idea of process 2, as long as node1 is reversed on the result of process 2.

  • To summarize: in the process of recursion, each layer actually reverses the direction of a node. The operation of each layer is consistent, so when the recursion is complete, the direction of the whole list is reversed.

With that in mind, the code becomes easier to implement:

# List reversal (recursion)
def reverse_recurse(node) :
    if node == None or node.next= =None:      # Recursive exit condition
        return node
    res = reverse_recurse(node.next)
    node.next.next = node                      Inverts the point of this object
    node.next = None                           # point this node to null
    return res
Copy the code

Test it out ~

# Reverse the list (recursion)
a = single_link([99.1.34.2.6.1.35.657.5.3.8.7])
b = reverse_recurse(a)
traverse(b) 
> [7.8.3.5.657.35.1.6.2.34.1.99]
Copy the code

3.2 Iterative Inversion

Similarly, take a linked list with 3 nodes as an example to sort out the thought:

  • The iteration process is easy to understand. Three variables need to be set, and the pointer of the CUR node should be moved forward in turn, and the pointer of the CUR node should be reversed each time. It should be noted that the forward node is necessary, so that after the linked list is disconnected, cur can move to the next node smoothly.

The implementation code is as follows:

# List reversal (iteration)
def reverse_iterate(node) :
    pre = None
    cur = node
    whilecur ! =None:                         # Traverse the list
        forward = cur.next                     # store a pointer to cur
        cur.next = pre                         # cur to pre
        pre = cur                              # pre move to the cur position
        cur = forward                          # cur move to next location
    return pre
Copy the code

Test it out ~

# Reverse the list (iteration)
a = single_link([99.1.34.2.6.1.35.657.5.3.8.7])
b = reverse_iterate(a)
traverse(b) 
> [7.8.3.5.657.35.1.6.2.34.1.99]
Copy the code

4 Single-linked list merge sort

  1. According to the recursive idea of merge sort, we need to pass the recursive process of the list is divided into a single node, and then through the process of sorting step by step, if you do not know the merge sort, you can refer to here: Python to implement the sequential table merge sort.
  2. Different from the merge operation of the sequential table, the single linked list can not be conveniently indexed to the middle node, only through the way of traversal, more trouble.

Take a single linked list of 5 nodes:

  • In the process of passing:

Pass the process is relatively simple, is the single list layer by layer. As long as the end node of the first half of the linked list points to NULL, the division can be completed.

  • In the process of returning:

The process of return is similar to the merging sort of the order table, create a new linked list, the node elements on the left and right are in turn smaller than the size, fill in the new list, the list is moved back one bit, then the size, and so on.

The implementation code is as follows:

def merge_sort(node) :
    if length(node) <= 1:           # Recursive exit condition
        return node
    split = length(node)//2-1       # Equinoxes (because python index starts at 0, so -1)
    cur1 = node
    cur2 = node.next
    for _ in range(split):          Move to the equinoxes
        cur1 = cur1.next
        cur2 = cur2.next
    cur1.next = None                # Point the end node of the first half to null
    left = merge_sort(node)
    right = merge_sort(cur2)
    return sort(left, right)        


def sort(left, right) :
    cur = Node(0)                             # Create a linked list with any value, and remove this node later
    head = cur
    whileleft ! =None andright ! =None:     # in order of size
        if left.element < right.element:
            cur.next = Node(left.element)
            cur = cur.next
            left = left.next                  
        else:
            cur.next = Node(right.element)
            cur = cur.next
            right = right.next
    ifleft ! =None:                           # Directly connect to the remaining nodes
        cur.next = left
    ifright ! =None:
        cur.next = right
    res = head.next                           
    head.next = None                           # Remove redundant head nodes
    return res
Copy the code

Test it out ~

Linked list merge sort
a = single_link([99.1.34.2.6.1.35.657.5.3.8.7])
b = merge_sort(a)
traverse(b)  
> [1.1.2.3.5.6.7.8.34.35.99.657]
Copy the code