A linked list of linear lists

Storage structure

An array ofNeed aContiguous memory spaceTo store, relatively high requirements for memory. If you apply for a 100MB array, the application fails even if the total available memory space is greater than 100MB if there is no contiguous or large enough storage space in the memory. whileThe listOn the contrary, it doesn’t require a contiguous memory space, itA series of discrete blocks of memory used by “Pointers”So if you are applying for a 100MB linked list, there will be no problem at all.

Singly linked lists

Linked lists use Pointers to concatenate a set of discrete chunks of memory. Among them, we takeBlocks of memory are called “nodes” of linked lists. In order to string all the nodes together, each of the linked listsIn addition to storing data, nodes also need to record the address of the next node in the chain. As the picture shows, we record thisThe pointer to the address of the next node is called next.The first node is called the head node and the last node is called the tail node. Among them,The header is used to record the base address of the linked list. And with that, you can iterate over the entire list. whileEnd nodeThe special point is that the pointer does not point to the next nodePoint to an empty address NULL, indicating that this is the last node on the list.

Insert and delete time complexity

In order to maintain the continuity of memory data, a large number of data moves are needed during the operation of array insertion and deletion, so the time complexity is O(n). To insert or delete data in a linked list, we do not need to move nodes in order to maintain the continuity of memory, because the storage space in a linked list is not contiguous. So, inserting and deleting a piece of data in a linked list is O(1).

Random access time complexity

Because the data in the linked list is not stored continuously, the corresponding memory address can not be directly calculated according to the initial address and subscript through the addressing formula like array. Instead, the corresponding node needs to be traversed according to the pointer node by node until the corresponding node is found.

Think of a linked list as a queue in which everyone only knows the person behind them, so to find out who the KTH person is, you need to start with the first person and count them down. Therefore, linked list random access performance is not as good as array, order n time complexity.

Circular linked list

The advantage of a circular list is that it is convenient to go from the end of the chain to the head of the chain. Circular lists are particularly useful when the data to be processed has a circular structure, such asJoseph problemPeople stand in a circle awaiting execution. The count begins at a specified point in the circle and proceeds around the circle in a specified direction. After skipping a specified number of people, the next person is executed. Repeat the process with the remaining people, starting with the next person and jumping over the same number of people in the same direction until only one person remains and is released.

# -*- coding: utf-8 -*- 
class Node(object) :
	def __init__(self, value) :
		self.value = value 
		self.next = None

def create_linkList(n) :
	head = Node(1)
	pre = head
	for i in range(2, n+1):
		newNode = Node(i)
		pre.next= newNode
		pre = newNode
	pre.next = head
	return head

n = 5 # total number
m = 2 # Number of numbers
if m == 1: # If the value is 1, special processing, direct output
	print (n)  
else:
	head = create_linkList(n)
	pre = None
	cur = head
	while cur.next! = cur:The terminating condition is that the next node of a node points to itself
		for i in range(m-1):
			pre =  cur
			cur = cur.next
		print (cur.value)
		pre.next = cur.next
		cur.next = None
		cur = pre.next
	print (cur.value)
Copy the code

Two-way linked list

Delete and insert

delete

Deleting a data from a linked list is one of two things:

• Delete a node whose value is equal to a given value:

In order to find the node whose value is equal to the given value, both single-linked lists and bidirectional linked lists need to start from the beginning node and compare one by one until the node whose value is equal to the given value is found and deleted. Although the time complexity of the simple deletion operation is O(1), the traversal search time is the main time consuming point, and the corresponding time complexity is O(n). According to the addition rule in time complexity analysis, the total time complexity of the linked list operation corresponding to the node whose value is equal to the given value is O(n).

• Deletes the node to which the given pointer points.

We have found the node to be deleted, but deleting a node Q requires knowing its precursor node, while a single linked list does not support directly obtaining the precursor node. Therefore, in order to find the precursor node, we still need to traverse the linked list from the beginning node until P ->next=q, indicating that P is the precursor node of Q. Nodes in a bidirectionally linked list already hold Pointers to their predecessors and do not need to be traversed like single-linked lists. Single-linked list deletion requires O(n) time complexity, whereas bidirectional lists require O(1) time complexity.

insert

Similarly, if a node is inserted in front of a specified node in a linked list, a bidirectional list can be done in O(1) time, whereas a unidirectional list requires O(n) time.

Bidirectional circular linked lists

Linked lists vs arrays

• Array is easy to use, in the implementation of the use of continuous memory space, you can use the CPU cache mechanism, preread the array of data, so the access efficiency is higher. Linked lists are not stored consecutively in memory, so they are not cache-friendly and do not prefetch efficiently — when the CPU reads data from memory, it loads it into the CPU’s cache first. Each time the CPU reads data from memory, it does not read only the address to be accessed. Instead, it reads a block of data and stores it in the CPU cache. The next time the CPU accesses data from memory, it starts to look in the CPU cache first. This enables a faster mechanism than memory access, which is why CPU caches exist: they were introduced to compensate for the difference between too slow memory access and too fast CPU execution. For arrays, the storage space is contiguous, so when you load a subscript, you can load the following subscript elements into the CPU cache, which is faster than if the storage space is not contiguous

Example of using linked lists

How to implement LRU cache with linked list

To maintain an ordered singly linked list, nodes closer to the end of the list are accessed earlier. When a new data is accessed, the list is traversed sequentially starting with the list header.

1. If the data has already been cached in the list, iterate to get the node corresponding to the data, remove it from its original position, and insert it into the head of the list.
2. If this data is not in the cache linked list, it can be divided into two cases:

• If the cache is not full at this point, the node is inserted directly into the head of the list;
• If the cache is full at this point, the end of the list is deleted and the new data node is inserted into the head of the list.

Because the linked list needs to be traversed regardless of whether the cache is full or not, the time complexity of the cache access based on the linked list is O(n).

How to determine palindrome strings with single linked lists

1. The fast and slow Pointers locate the middle nodes
2. Reverse from the middle node to the back half
3. Compare the front and back parts to determine whether it is palindrome
4. The latter half is reversely restored

Time complexity O(n), space complexity O(1)

Tips for writing linked list code

Clear pointer meaning

Assigning a variable to a pointer is essentially assigning the address of the variable to the pointer, or conversely, the pointer holds the memory address of the variable, points to the variable, and the pointer finds the variable.

Be alert for pointer loss and memory leaks

p->next = x;  // set p's next pointer to x;
x->next = p->next;  // next pointer on node x to node b;
Copy the code

After the first step, the p->next pointer no longer points to node B, but to node X. Line 2 is equivalent to assigning x to x->next, pointing to itself. So the whole list is split in half, and all nodes from node B onwards are inaccessible. When inserting nodes, we must pay attention to the order of operation. We should first point the next pointer of node X to node B, and then point the next pointer of node A to node X, so as not to lose the pointer and cause memory leakage. So for the insert we just did, we just reversed the order of line 1 and line 2. Similarly, when deleting linked list nodes, you must also remember to manually free up memory space, otherwise, memory leaks will also occur.

Use sentries to simplify the implementation

For the insertion and deletion operations of linked lists, special treatment is required for inserting the first node and deleting the last node, such as:

if (head == null) {
  head = new_node;
}// Insert a node into an empty list
Copy the code

if (head->next == null) {
   head = null;
}// Delete the last node
Copy the code

If you introduce a sentinel node, the head pointer will always point to that sentinel node regardless of whether the list is empty or not. We also call this type of list with sentinel nodes a lead list. Conversely, a list without sentries is called an unheaded list.

The sentinel node does not store data. Because the sentinel node is always there, inserting the first node and inserting the other nodes, deleting the last node and deleting the other nodes, can be unified into the same code implementation logic.

Examples comparison

// In array A, find the key, return the location of the key
// where n represents the length of array A
int find(char* a, int n, char key) {
  // If a is null, or n<=0, there is no data in the array
  if(a == null || n <= 0) {
    return - 1;
  }
  
  int i = 0;
  I 
  while (i < n) {
    if (a[i] == key) {
      return i;
    }
    ++i;
  }
  
  return - 1;
}
Copy the code

// In array A, find the key, return the location of the key
// where n represents the length of array A
// Take two examples
// a = {4, 2, 3, 5, 9, 6} n=6 key = 7
// a = {4, 2, 3, 5, 9, 6} n=6 key = 6
int find(char* a, int n, char key) {
  if(a == null || n <= 0) {
    return - 1;
  }
  
  // The value of a[n-1] will be replaced by key
  if (a[n- 1] == key) {
    return n- 1;
  }
  
  // Temporarily store the value of a[n-1] in the TMP variable for later recovery. TMP = 6.
  // The reason for doing this is that the find() code does not change the contents of the A array
  char tmp = a[n- 1];
  // insert key into a[n-1] where a = {4, 2, 3, 5, 9, 7}
  a[n- 1] = key;
  
  int i = 0;
  // The while loop has fewer I 
  while(a[i] ! = key) { ++i; }A = {4, 2, 3, 5, 9, 6}
  a[n- 1] = tmp;
  
  if (i == n- 1) {
    // If I == n-1, 0... There is no key between n and 2, so -1 is returned
    return - 1;
  } else {
    // Otherwise, return I, the index of the element equal to key
    returni; }}Copy the code

By using a sentry a[n-1] = key, the comparison statement I <n is successfully omitted. Do not take this statement lightly, when the cumulative execution of thousands of times, hundreds of thousands of times, the cumulative time is obvious. Of course, this is just an example of what sentinels can do. Never write code that looks like the second paragraph, because it’s not very readable.

Pay special attention to boundary condition processing

• Does the code work if the list is empty?
• Does the code work if the linked list contains only one node?
• Does the code work if the linked list contains only two nodes?
• Does the code logic work when dealing with heads and tails?

Concrete drawing, to aid thinking

source

Time.geekbang.org/column/arti… Time.geekbang.org/column/arti…