Sequence lists and linked lists
1. Linear table
A linear list (linear list) is a finite sequence of n data elements with the same characteristics. Linear table is a data structure widely used in practice. Common linear tables: sequential list, linked list, stack, queue, string…
A linear table is logically a linear structure, that is, a continuous straight line. However, the physical structure is not necessarily continuous. When linear tables are physically stored, they are usually stored in the form of arrays and linked structures.
2. Sequence table
2.1 Concept and structure
A sequence table is a linear structure that uses a storage unit with continuous physical addresses to store data elements in sequence. Generally, array storage is used.
Store. Complete the addition, deletion, checking and modification of data on the array.
The sequence table can generally be divided into:
\1. Static sequence list: Use fixed-length arrays to store elements.
\2. Dynamic sequence table: Use dynamically opened array storage.
2.2 Interface implementation
Static sequence tables are only suitable for scenarios where you know how much data needs to be stored. The fixed-length array of the static sequence table causes N to be too large. If the space is too much, it is wasted, and if it is too little, it will not be enough. Therefore, in reality, dynamic sequence tables are basically used to dynamically allocate space according to needs, so below we implement dynamic sequence tables.
typedef int SLDataType;
//Dynamic storage of sequence table
typedef struct SeqList
{<!-- -->
SLDataType* array; // Points to a dynamically allocated array
size_t size; // Number of valid data
size_t capacity; //The size of the capacity space
}SeqList;
//Basic add, delete, check and modify interface
//Sequence table initialization
void SeqListInit(SeqList* psl);
// Check the space, if it is full, increase the capacity
void CheckCapacity(SeqList* psl);
//Insert at the end of the sequence table
void SeqListPushBack(SeqList* psl, SLDataType x);
//Delete at the end of the sequence table
void SeqListPopBack(SeqList* psl);
// Insert sequence header
void SeqListPushFront(SeqList* psl, SLDataType x);
//Delete sequence header
void SeqListPopFront(SeqList* psl);
//Sequence table lookup
int SeqListFind(SeqList* psl, SLDataType x);
// The sequence table inserts x at position pos
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
//Delete the value of pos position in the sequence table
void SeqListErase(SeqList* psl, size_t pos);
//Sequence list destroyed
void SeqListDestory(SeqList* psl);
// Print sequence table
void SeqListPrint(SeqList* psl);
Head plug implementation:
The implementation of head insertion requires first moving the data in the sequence table back one by one, and then inserting the data into the position with subscript 0.
Header deletion implementation:
Head deletion only needs to overwrite the data in the sequence table one by one. Note that you need to reduce the effective number in the sequence table by 1, that is, ps->size-1.
The sequence table inserts x at position pos:
Delete the value of pos position in the sequence table:
2.3 Sequence table expansion
There are two situations when the sequence table is expanded using realloc:
- There is enough memory space at the back: expand in place, and the starting address remains unchanged after expansion.
- The back space is not enough for expansion: remote expansion, the starting address changes after expansion.
2.4 Questions and Thoughts on Sequence Lists
question:
advantage:
- End insertion and end deletion are fast enough
- Random access and modification of subscripts
shortcoming:
- The efficiency of insertion and deletion in the middle/head is too low, and the time complexity is O(N)
- Capacity expansion (especially off-site expansion) requires applying for new space, copying data, and releasing old space. There will be a lot of consumption.
- Expansion is generally a 2-fold increase, and there will inevitably be a certain amount of wasted space. For example, the current capacity is 100, and when it is full, it will be expanded to 200. If we continue to insert 5 data, and no data will be inserted later, 95 data spaces will be wasted.
Thinking: How to solve the shortcomings of the above problems? The structure of the linked list is given below to take a look.
3. Linked list
3.1 The concept and structure of linked lists
Concept: A linked list is a physically non-continuous and non-sequential storage structure. The logical sequence of data elements is through pointer links in the linked list. strong>Achieved sequentially.
Physical structure:
Notice:
- As can be seen from the above figure, the chain structure is logically continuous, but not necessarily physically continuous.
- In reality, nodes are generally applied from the heap.
- The space requested from the heap is allocated according to a certain strategy. The space applied for twice may be continuous or discontinuous.
Assuming that on a 32-bit system, the value field in the node is of type int, then the size of a node is 8 bytes, then there may also be the following linked list:
3.2 Classification of linked lists
In practice, the structures of linked lists are very diverse. There are 8 types of linked list structures when combined with the following situations:
\1. One-way or two-way
\2. Take the lead or not
\3. Loop or non-loop
Although there are so many linked list structures, there are two structures we most commonly use in practice:
reason
- Headless one-way acyclic linked list: simple structure, generally not used to store data alone. In practice, it is more often used as a substructure of other data structures, such as hash buckets, adjacency lists of graphs, etc. In addition, this structure appears a lot in written interviews.
- Headed two-way circular linked list: the most complex structure, generally used to store data separately. The linked list data structures used in practice are all headed bidirectional circular linked lists. In addition, although this structure is complex, after using the code to implement it, you will find that the structure will bring many advantages, and the implementation will be simple. We will know it later when we implement the code.
3.3 Implementation of one-way linked list
// 1. Headless + one-way + non-cyclic linked list implementation of addition, deletion, query and modification
typedef int SLTDateType;
typedef struct SListNode
{<!-- -->
SLTDateType data;
struct SListNode* next;
}SListNode;
// Dynamically apply for a node
SListNode* BuySListNode(SLTDateType x);
//Singly linked list printing
void SListPrint(SListNode* plist);
//Insert at the end of single linked list
void SListPushBack(SListNode** pplist, SLTDateType x);
// Header of singly linked list
void SListPushFront(SListNode** pplist, SLTDateType x);
//Tail deletion of singly linked list
void SListPopBack(SListNode** pplist);
//Delete single linked list header
void SListPopFront(SListNode** pplist);
//Singly linked list search
SListNode* SListFind(SListNode* plist, SLTDateType x);
//Insert x after pos position in singly linked list
// Analyze and think about why not insert before pos position?
void SListInsertAfter(SListNode* pos, SLTDateType x);
//Singly linked list deletes the value after pos position
// Analyze and think about why the pos position is not deleted?
void SListEraseAfter(SListNode* pos);
3.4 Interface implementation of one-way linked list
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//Print
void SLTPrint(SLTNode*phead)
{<!-- -->
SLTNode* cur = phead;
//while (cur != NULL)
while (cur)
{<!-- -->
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\\
");
}
SLTNode* BuySListNode(SLTDataType x)
{<!-- -->
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{<!-- -->
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
End insertion phead is the formal parameter of plist //There is a linked list at the beginning
//void SLTPushBack(SLTNode* phead, SLTDataType x)
//{<!-- -->
// SLTNode* newnode = BuySListNode(x);
// SLTNode* tail = phead;
// while (tail->next != NULL)
// {<!-- -->
// tail = tail->next;
// }
// tail->next = newnode;
//}
//Tail insert //Including no linked list at the beginning
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{<!-- -->
//pphead does not exist, so it must be asserted
assert(pphead);
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{<!-- -->
//Change the pointer of the structure, so use a secondary pointer
*pphead = newnode;
}
else
{<!-- -->
SLTNode* tail = *pphead;
while (tail->next != NULL)
{<!-- -->
tail = tail->next;
}
//To change the structure, use the pointer of the structure.
tail->next = newnode;
}
}
//Head plug
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{<!-- -->
//pphead does not exist, so it must be asserted
assert(pphead);
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
//Delete tail
void SLTPopBack(SLTNode** pphead)
{<!-- -->
//There is no empty situation for pphead, so it must be asserted
assert(pphead);
//1.Empty
assert(*pphead);
//2. A node
//3. More than one node
if ((*pphead)->next == NULL)
{<!-- -->
free(*pphead);
*pphead = NULL;
}
else
{<!-- -->
\t\t//method 1.
SLTNode* tailPrev = NULL;
SLTNode* tail = *pphead;
while (tail->next)
{<!-- -->
tailPrev = tail;
tail = tail->next;
}
free(tail);
tailPrev->next = NULL;
\t\t
Method 2.
//SLTNode* tail = *pphead;
//while (tail->next->next)
//{<!-- -->
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
}
}
//Delete header
void SLTPopFront(SLTNode** pphead)
{<!-- -->
//pphead does not exist, so it must be asserted
assert(pphead);
\t//null
assert(*pphead);
\t//non empty
SLTNode* newhead = (*pphead)->next;
free(*pphead);
*pphead = newhead;
}
//Find if there is a number x, find it and return a pointer to the number
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{<!-- -->
SLTNode* cur = phead;
while (cur)
{<!-- -->
if (cur->data == x)
{<!-- -->
return cur;
}
cur = cur->next;
}
return NULL;
}
//Insert before pos position
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{<!-- -->
//pphead does not exist, so it must be asserted
assert(pphead);
assert(pos);
if (pos == *pphead)
{<!-- -->
SLTPushFront(pphead, x);
}
else
{<!-- -->
SLTNode* prev = *pphead;
while (prev->next != pos)
{<!-- -->
prev = prev->next;
}
SLTNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
//Insert after pos position
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{<!-- -->
assert(pos);
SLTNode* newnode = BuySListNode(x);
\t
//The following two sentences cannot exchange positions, otherwise they will form a loop.
newnode->next = pos->next;
pos->next = newnode;
}
//Delete pos position
void SLTErase(SLTNode** pphead, SLTNode* pos)
{<!-- -->
//pphead does not exist, so it must be asserted
assert(pphead);
assert(pos);
if (*pphead == pos)
{<!-- -->
SLTPopFront(pphead);
}
//else if (pos->next == NULL)
//{<!-- -->
//SLTPopBack(pphead);
//}
else
{<!-- -->
SLTNode* prev = *pphead;
while (prev->next != pos)
{<!-- -->
prev = prev->next;
}
//free(prev->next);//Don’t free, otherwise this node will be gone
prev->next = pos->next;
}
}
//Delete the position after pos
void SLTEraseAfter(SLTNode* pos)
{<!-- -->
//
assert(pos);
//Check whether pos is the tail node
//assert(pos->next);//Violent detection
if (pos->next == NULL)//Gentle detection
{<!-- -->
return NULL;
}
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}
//Without header, delete pos position
void SLTEraseNoFront(SLTNode* pos)
{<!-- -->
//Check whether pos is the tail node
//assert(pos->next);//Violent detection
if (pos->next == NULL)//Gentle detection
{<!-- -->
return NULL;
}
SLTNode* posNext = pos->next;
pos->data = posNext->data;
pos->next = posNext->next;
free(posNext);
posNext = NULL;
}
void SLTDestroy(SLTNode** pphead)
{<!-- -->
assert(pphead);
SLTNode* cur = *pphead;
while (cur)
{<!-- -->
SLTNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
3.5 Implementation of doubly linked list
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 2. Take the lead + two-way + circular linked list implementation of addition, deletion, checking and modification
typedef int LTDataType;
typedef struct ListNode
{<!-- -->
LTDataType_data;
struct ListNode* next;
struct ListNode* prev;
}ListNode;
//Create the head node of the returned linked list.
ListNode* ListCreate();
// Destroy doubly linked list
void ListDestory(ListNode* plist);
//Print doubly linked list
void ListPrint(ListNode* plist);
//Insert at the end of the doubly linked list
void ListPushBack(ListNode* plist, LTDataType x);
// Delete the end of the doubly linked list
void ListPopBack(ListNode* plist);
// Insert the head of the two-way linked list
void ListPushFront(ListNode* plist, LTDataType x);
// Delete the header of the doubly linked list
void ListPopFront(ListNode* plist);
//Doubly linked list search
ListNode* ListFind(ListNode* plist, LTDataType x);
// Doubly linked list is inserted in front of pos
void ListInsert(ListNode* pos, LTDataType x);
// Delete the node at pos position in the doubly linked list
void ListErase(ListNode* pos);
//List size
int LTSize(LTNode* phead);
//Find pos location
LTNode* LTFind (LTNode* phead, LTDataType x);
//destroy
LTNode* LTDetory(LTNode* phead);
3.6 Interface implementation of doubly linked list
LTNode* BuyLTNode(LTDataType x)
{<!-- -->
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{<!-- -->
perror("malloc fail");
exit(-1);
}
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
}
LTNode* LTInit()
{<!-- -->
LTNode* phead = BuyLTNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}
//Print
void LTPrint(LTNode*phead)
{<!-- -->
assert(phead);
printf("phead<=>");
LTNode* cur = phead->next;
while (cur != phead)
{<!-- -->
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("\\
");
}
//Tail insertion
void LTPushBack(LTNode* phead, LTDataType x)
{<!-- -->
assert(phead);
//LTNode* tail = phead->prev;
//LTNode* newnode = BuyLTNode(x);
//newnode->prev = tail;
//tail->next = newnode;
//newnode->next = phead;
//phead->prev = newnode;
//Insert in front of the phead position (that is, the end of the linked list), which is equivalent to tail insertion
LTInsert(phead, x);
}
//Delete tail
void LTPopBack(LTNode*phead)
{<!-- -->
assert(phead);
assert(phead->next != phead);
/*LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;*/
//Deleting the node at phead->prev position is equivalent to tail deletion
LTErase(phead->prev);
}
//Head plug
void LTPushFront(LTNode* phead, LTDataType x)
{<!-- -->
assert(phead);
//LTNode* newnode = BuyLTNode(x);
//newnode->next = phead->next;
//phead->next->prev = newnode;
//phead->next = newnode;
//newnode->prev = phead;
//LTNode* newnode = BuyLTNode(x);
//LTNode* first = phead->next;
phead newnode first
//phead->next = newnode;
//newnode->prev = phead;
//newnode->next = first;
//first->prev = newnode;
//Insert in front of phead->next position, which is equivalent to head insertion
LTInsert(phead->next, x);
}
//Delete header
void LTPopFront(LTNode* phead)
{<!-- -->
assert(phead);
assert(phead->next != phead);
//LTNode* first = phead->next;
//LTNode* second = first->next;
//free(first);
//phead->next = second;
//second->prev = phead;
//Delete the node at phead->next position, which is equivalent to head deletion
LTErase(phead->next);
}
int LTSize(LTNode*phead)
{<!-- -->
assert(phead);
int size = 0;
LTNode* cur = phead->next;
while (cur != phead)
{<!-- -->
+ + size;
cur = cur->next;
}
return size;
}
//Insert forward from pos position
void LTInsert(LTNode* pos, LTDataType x)
{<!-- -->
\t
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* newnode = BuyLTNode(x);
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
\t
}
//Delete from pos position
void LTErase(LTNode* pos)
{<!-- -->
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{<!-- -->
assert(phead);
LTNode* cur = phead->next;
while (cur!=phead)
{<!-- -->
if (cur->data == x)
{<!-- -->
return cur;
}
cur = cur->next;
}
return NULL;
}
//destroy
LTNode* LTDetory(LTNode* phead)
{<!-- -->
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{<!-- -->
//next = cur->next;
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
4. The difference between sequence lists and linked lists
Note: Cache utilization refers to the storage architecture and local principles.
Extended knowledge: “CPU cache knowledge relevant to programmers” https://coolshell.cn/articles/20793.html