This article has been synchronized with simple book iOS – linked list

Linkedlist is a common basic data structure. It is a linear list and a non-continuous and non-sequential storage structure on a physical storage unit. The logical order of data elements is achieved by linking the order of Pointers in a linked list, but data is not stored in a linear order. Linked lists usually consist of a series of nodes, each containing arbitrary instance data datafields and one or two links that point to the location of the previous or next node. In computer science, linked list, as a basic data structure, can be used to generate other types of data structure. The interrelation between the data makes linked list divided into three types: single linked list, circular linked list and bidirectional linked list

The most basic structure of a linked list is to store data at each node to the address of the next node, and a special closing tag at the last node. In addition, the pointer to the first node is stored in a fixed location, sometimes also store the pointer to the last node. But you can also save the location of a node in advance, and then directly access, of course, if only access data is not necessary, as in the linked list error pointer to the actual data. This is usually done to access the next or previous node in the list

Advantage: Can overcome the array list need to know in advance the disadvantage of data size, chain table structure can make full use of computer memory space, realize flexible dynamic memory management list of the most obvious benefit is that regular array arrangement related projects may differ from these data in memory or on disk order, array access tend to be in a different order of conversion. A list is a self-indicating data type because it contains Pointers (links) to another data type of the same type, and linked lists allow insertion and removal of nodes anywhere on the table.

Disadvantages: The linked list has a large space overhead due to the addition of pointer fields of nodes. In addition, the linked list loses the advantage of random array reading. Generally, when searching a node, you need to start from the first node and visit the next node each time until you reach the desired location

#### One-way linked lists The simplest type of linked list is a one-way linked list

A one-way linked list node is divided into two parts. It contains two fields, an information field and a pointer field. The first part holds or displays information about the node, the second node stores the address of the next node, and the last node points to a null value. A one-way linked list can only traverse in one direction

Singly linked lists have a head, a head node address list in the memory of the first, every node in the list of the data type of structure type, the node has two members: members of the integer (actual need save data) and pointer to a structure type node under the next node address (in fact, the singly linked list is used to store the integer data of dynamic array). According to this structure, the access to each node in the linked list should start from the head of the list, and the address of the subsequent node is given by the current node. Whenever you access any node in the table, you need to start at the head of the list and look backwards. Since there is no subsequent node, the pointer field of the last node of the linked list is empty and written as NULL

The above figure also shows that the storage address of each node in the linked list is not continuous. The address of each node is allocated to the system when it is needed. According to the current situation of the memory, the system can allocate the address consecutively or by skipping

Realization of one-way list program ######1. Data structure definition of linked list node

Class ListNode {var val: Int var next:ListNode? init(_ val: Int) { self.val = val self.next = nil } }Copy the code

In the definition of a linked list node, the member Next is a pointer to exactly the same type of node, except for an integer member

In the data structure of the linked list node, a very special point is that the data type of the pointer field in the structure body uses an unsuccessful data type. This is the only data structure in C that can be used first and defined later ######2. The process of creating a singly linked list includes the following steps:

  1. Define the data structure of the linked list
  2. Create an empty table
  3. The malloc function is used to assign a node to the system
  4. Sets the pointer member of the new node to null. If the table is empty, connect the new node to the table header. If the table is not empty, connect the new node to the end of the table
  5. Check whether any subsequent nodes are to be added to the linked list. If so, go to3. , otherwise end

######3. The output process of a singly linked list has the following steps

  1. Find the header
  2. Outputs the value member of the node if the table is not empty, and exits if the table is empty
  3. Track the growth of the linked list by finding the address of the next node
  4. Go to the 2

######4. Complete code to create a store positive integer single linked list, enter 0 or less than 0, end the creation of the list, and print the list

// // ListNode.c // AlgorithmDemo // // Created by Ternence on 2021/5/7. // #include "ListNode.h" #include <stdlib.h> // #include <stdio.h> struct Node {int num; struct Node *next; }; main() { void print(); struct Node *head; // create an empty table head = NULL; //head = create(head); print(head); } struct Node *create(struct Node *head) { struct Node *p1, *p2; P1 = p2 = (struct Node *)malloc(sizeof(struct Node)); printf("p1 = %d \n", p1); scanf("%d", &p1 -> num); P1 ->next = NULL; While (p1->num > 0) {p1->num > 0; p1->num > 0; If (head == NULL) {head = p1; } else {p2 -> next = p1; P2 = p1; p1 = (struct Node *)malloc(sizeof(struct Node)); } printf("p2 = %d \n", p2); // Enter the value of the node scanf("%d", &p1->num); If (p1 -> num <= 0) {p1 = NULL; p2 -> next = NULL; break; } } printf("p2 > next = %d \n", p2->next); return head; Void print(struct Node *head) {struct Node *temp; // Get the head pointer of the list temp = head; while (temp ! Printf ("%d \n ", temp->num); temp = temp -> next; }}Copy the code

In the process of creating a linked list, the head pointer of the linked list is a very important parameter, because the output and search of the linked list should start from the head of the list, so after the list is created successfully, the address of a linked list node should be returned, that is, the head pointer program execution flow:

#### Bidirectional linked list Bidirectional linked list is actually an improvement of a single linked list, when we operate on a single linked list, sometimes you need to operate on the direct precursor of a node, and you have to start from the table header. This is limited by the structure of single-linked list nodes, because each single-linked list node has only one chain domain that stores the address of the direct successor node. So can we define a double-linked node structure that has both the chain domain that stores the address of the direct successor node and the chain domain that stores the address of the direct precursor node? So that’s a two-way list

In a bidirectional linked list, there are two chain fields besides the data domain. One stores the address of the immediate successor node, which is generally called the right chain field (when this “join” is the last “join”, it points to a null value or an empty list). A bidirectional list node definition that stores the address of a direct precursor node, called a left linked field (pointing to a null value or an empty list when this “connection” is the first “connection”)

struct Node { int data; struct Node *llink, *rlink; //llink is left link; rlink is right link;Copy the code

Of course, it is also possible to form a bidirectional circular list from a bidirectional list. Bidirectional lists, like unidirectional lists, have three basic operations: find, insert, and delete

#### Circular list A circular list is a linked storage structure like a one-way list. The difference is that the pointer to the last node of the circular list points to the first node or the head node of the circular list, thus forming a circular chain

The operations of circular linked lists are basically the same as those of single linked lists, with the following differences:

  1. When creating a circular list, the pointer to the last node must be set to the head node rather than NULL as in a single list. This is also used when a new node is inserted after the last node
  2. When judging whether to reach the end of the table, it is to determine whether the value of the chain field of the node is the head node. When the value of the chain field is equal to the head pointer, it indicates that the node has reached the end of the table, rather than whether the value of the chain field is NULL like that of a single linked list

#### block list A block list is itself a linked list, but a linked list stores not general data, but a sequential list made up of that data. Each node of a block-linked list, that is, a sequential list, can be called a block

Another feature of block lists is that they save memory compared to regular lists because they do not store Pointers to every data node

The time complexity of insertion and deletion in sequential storage is linear time, while the operation of linked list can be constant time complexity

Insert and delete operation sequence of linked list:

  • Insert operations are processed in order: logic of the middle node, logic of the back node, logic of the front node
  • Delete operations are processed in the following order: logic of the front node, logic of the back node, and logic of the middle node

Reference :ios – A simple understanding of linked lists