Table of Contents
The definition of linear tables and their basic operations (sequential table insertion, deletion, search, modification)
4. Linked storage structure of linear table
1. Single linked list
2. Circular linked list
3. Doubly linked list
a. Doubly linked list node structure
b. Create a new node
c. Insert node at the end of the linked list
d. Insert a node at the specified position
e. Delete the node at the specified location
f. Traverse and print the linked list
g. Main function
h. Code integration
5. Complexity Analysis
1. Space efficiency comparison
2. Time efficiency comparison
The definition of a linear table and its basic operations (sequential table insertion, deletion, search, modification)
A linear list is an ordered set of zero or more nodesof the same type.
The storage method of sequentially storing the linear table nodes in a group of storage units with consecutive addresses according to the logical order between them is called the sequential storage method of the linear table. Linear tables stored in sequential storage have a sequential storage structure and are generally called sequential tables. In other words, a linear table that uses a fixed-length one-dimensional array and stores it in a sequential manner is called a sequential table.
[Data Structure] Linear Table (1) The definition of linear table and its basic operations (sequential table insertion, deletion, search, modification) – CSDN Blog
https:/ /blog.csdn.net/m0_63834988/article/details/132089038?spm=1001.2014.3001.5501
4. Linked storage structure of linear table
1. Single linked list
The advantage of the sequence table is fast access speed. However, whether you are inserting a node or deleting a node, you need to adjust the addresses of a batch of nodes. To overcome this shortcoming, a storage method different from sequential storage must be provided. A linear list stored using linked storage is called a linked list, which can overcome the above shortcomings.
The nodes in the linked list are stored in storage units (several consecutive bytes). The storage units can be continuous (in storage space) or discontinuous, or even scattered in the storage space. any position. In other words, there is no necessary connection between the logical order and the physical order of the nodes in the linked list. The most important thing is that the linked list can add and delete nodes at any time as needed without moving the node position, and dynamically adjust it.
[Data structure] Linear table (2) Single linked list and its basic operations (create, insert, delete, modify, traverse and print) – CSDN Bloghttps:// blog.csdn.net/m0_63834988/article/details/133914875?spm=1001.2014.3001.5501
2. Circular linked list
Starting from a node in a singly linked list, you can only access the nodes linked behind it, but cannot access the nodes located in front of it, which is very inconvenient for some practical applications. The solution is to “circulate” the link structure, that is, store the pointer to the sentinel node in the next field of the end node of the list instead of storing the null pointer NULL. Such a singly linked list is called a circular linked list. Circular linked lists allow users to access any node in the linked list starting from any position in the linked list.
?
[Data structure] Linear table (3) Various operations of circular linked list (create, insert, search, delete, modify, traverse and print, release memory space) – CSDN Bloghttps://blog.csdn.net/m0_63834988/article/details/133914085?spm=1001.2014.3001.5501
3. Doubly linked list
In a circular linked list, starting from a node, the entire linked list must be traversed to find its predecessor node, and the time complexity is O(n). A doubly linked list will solve this problem well. The so-called doubly linked list means that any node P in the linked list is composed of the data field, the left pointer field left (pre) and the right pointer field right (next). The left pointer field and the right pointer field store the left and right sides of P respectively. Address information of adjacent nodes.
?
The advantage of a doubly linked list is that a node can be deleted or inserted in constant time, because only the front and rear pointers of the node need to be modified, and there is no need to traverse to a specified position like a one-way linked list. In a one-way linked list, deleting or inserting a node requires first finding the previous node and then modifying the pointer. However, doubly linked lists require more memory space to store additional pointers than singly linked lists. In addition, because there is one more pointer, inserting and deleting nodes requires more operations.
a. Doubly linked list node structure
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
Contains an integer data and two pointers prev and next, pointing to the previous node and the next node respectively.
b. Create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
Creates a new node that accepts an integer as argument and allocates memory to store the node. Then, the node’s data is set to the integer passed in, and the prev and next pointers are initialized to NULL. Finally, the newly created node pointer is returned.
c. Insert node at the end of the linked list
void append(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
Node* current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
newNode->prev = current;
}
}
- Create a new node and use the passed integer as the node’s data.
- Check if linked list is empty
- If it is empty, point the head pointer of the linked list to the new node;
- Otherwise, traverse the linked list to find the last node, point the
nextpointer of the last node to the new node, and point theprevpointer of the new node to the last node.
d. Insert node at the specified position
void insert(Node** head, int data, int position) {
Node* newNode = createNode(data);
if (position == 0) {
newNode->next = *head;
if (*head != NULL) {
(*head)->prev = newNode;
}
*head = newNode;
} else {
Node* current = *head;
int i;
for (i = 0; i < position - 1 & amp; & amp; current != NULL; i + + ) {
current = current->next;
}
if (current == NULL) {
printf("Invalid position\
");
return;
}
newNode->next = current->next;
newNode->prev = current;
if (current->next != NULL) {
current->next->prev = newNode;
}
current->next = newNode;
}
}
- Create a new node and use the passed integer as the node’s data.
- If the insertion position is 0, it means inserting a new node at the head of the linked list
- Point the
nextpointer of the new node to the head node of the linked list - If the linked list is not empty, point the
prevpointer of the head node of the linked list to the new node, and finally point the head pointer of the linked list to the new node.
- Point the
- If the insertion position is not 0
- First traverse the linked list to find the previous node at the insertion position
- If the position is found or the specified position is not found after traversing to the end of the linked list, “Invalid position” is output and returned.
- Otherwise, point the
nextpointer of the new node to the node pointed to by thenextpointer of the current node, and point theprevpointer of the new node to the current node. - If the
nextpointer of the current node is not empty, point theprevpointer of the node pointed by thenextpointer of the current node to the new node, and finally point the Thenextpointer of the current node points to the new node.
e. Delete the node at the specified position
void delete(Node** head, int position) {
if (*head == NULL) {
printf("List is empty\
");
return;
}
Node* temp = *head;
if (position == 0) {
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
} else {
int i;
for (i = 0; i < position & amp; & amp; temp != NULL; i + + ) {
temp = temp->next;
}
if (temp == NULL) {
printf("Invalid position\
");
return;
}
temp->prev->next = temp->next;
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
free(temp);
}
}
- If the linked list is empty, output “List is empty” and return.
- If the node to be deleted is the head node of the linked list
- Point the head pointer of the linked list to the next node of the head node. If the linked list is not empty, point the
prevpointer of the new head node toNULL, and then release the deleted node. of memory.
- Point the head pointer of the linked list to the next node of the head node. If the linked list is not empty, point the
- If the node to be deleted is not the head node
- First traverse the linked list to find the node to be deleted
- If the node at the specified position is found or is not found after traversing to the end of the linked list, “Invalid position” is output and returned.
- Otherwise, the
nextpointer of the node before the node to be deleted points to the node next to the node to be deleted. If the node next to the node to be deleted is not empty, thepointer of the node next to the node to be deleted is not empty. The >prevpointer points to the node before the node to be deleted. - Finally release the memory of the node to be deleted.
f. Traverse and print the linked list
void printList(Node* head) {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\
");
}
Starting from the head node of the linked list, by continuously accessing the next pointer, print the data of each node and move to the next node until the entire linked list is traversed.
g. main function
int main() {
Node* head = NULL;
printList(head);
//Insert node at the end of the linked list
append( & amp;head, 1);
append( & amp;head, 2);
append( & amp;head, 3);
printList(head);
//Insert node at specified position
insert( & amp;head, 4, 1);
printList(head);
//Delete the node at the specified position
delete( & amp;head, 2);
printList(head);
return 0;
}
?
h. Code integration
#include#include //Doubly linked list node structure typedef struct Node { int data; struct Node* prev; struct Node* next; } Node; //Create a new node Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->prev = NULL; newNode->next = NULL; return newNode; } //Insert node at the end of the linked list void append(Node** head, int data) { Node* newNode = createNode(data); if (*head == NULL) { *head = newNode; } else { Node* current = *head; while (current->next != NULL) { current = current->next; } current->next = newNode; newNode->prev = current; } } //Insert node at specified position void insert(Node** head, int data, int position) { Node* newNode = createNode(data); if (position == 0) { newNode->next = *head; if (*head != NULL) { (*head)->prev = newNode; } *head = newNode; } else { Node* current = *head; int i; for (i = 0; i < position - 1 & amp; & amp; current != NULL; i + + ) { current = current->next; } if (current == NULL) { printf("Invalid position\ "); return; } newNode->next = current->next; newNode->prev = current; if (current->next != NULL) { current->next->prev = newNode; } current->next = newNode; } } //Delete the node at the specified position void delete(Node** head, int position) { if (*head == NULL) { printf("List is empty\ "); return; } Node* temp = *head; if (position == 0) { *head = (*head)->next; if (*head != NULL) { (*head)->prev = NULL; } free(temp); } else { int i; for (i = 0; i < position & amp; & amp; temp != NULL; i + + ) { temp = temp->next; } if (temp == NULL) { printf("Invalid position\ "); return; } temp->prev->next = temp->next; if (temp->next != NULL) { temp->next->prev = temp->prev; } free(temp); } } // Traverse and print the linked list void printList(Node* head) { Node* current = head; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\ "); } // main function int main() { Node* head = NULL; printList(head); //Insert node at the end of the linked list append( & amp;head, 1); append( & amp;head, 2); append( & amp;head, 3); printList(head); //Insert node at specified position insert( & amp;head, 4, 1); printList(head); //Delete the node at the specified position delete(&head, 2); printList(head); return 0; }
5. Complexity Analysis
So far, this series has introduced in detail the two storage methods of linear tables – sequential storage and linked storage. The following is a comparative analysis of the two in terms of space and time complexity.
1. Space efficiency comparison
The space occupied by the sequence table comes from the applied array space, and the array size is determined in advance. Obviously, when there are few elements in the table, a lot of space in the sequence table is idle, resulting in a waste of space;
The space occupied by the linked list is dynamically applied for as needed, and there is no problem of wasting space. However, the linked list needs to attach a pointer field to each node, thereby increasing a certain amount of space overhead.
2. Time efficiency comparison
The basic operations of linear tables are access, insertion and deletion. For sequential lists, random access is very easy, but every time an element is inserted or deleted, several elements need to be moved.
For linked lists, random access cannot be achieved. The linked list must be traversed from the head until the element to be accessed is found. However, the insertion and deletion operations of the linked list are very simple and only require modifying a few pointers.
- When insertion and deletion operations on linear lists are often required, linked lists are more time efficient;
- Doubly linked lists are more flexible and efficient in certain scenarios, especially when frequent insertion and deletion operations are required. However, where memory is limited, a one-way linked list may be more appropriate.
- When linear tables are often accessed and access operations are more frequent than insertion and deletion operations, sequential tables are more time efficient.