The sequential table uses the adjacency relation of array elements at the physical position (that is, array subscript) to represent the logical relation between data elements in a linear table, which makes the sequential table have the following disadvantages:

① Insert and delete operations need to move a large number of elements. Insert and delete operations (O(n)) on a sequential table with equal probability require, on average, half of the table’s elements to be moved.

② The capacity of the table is difficult to determine. Since the length of the array must be determined in advance (dynamic allocation solves this problem), it is difficult to determine the appropriate storage size when the length of a linear table varies greatly.

③ The storage space is fragmented. Arrays must occupy continuous storage space. Even if the number of storage units exceeds the required number, they cannot be used if they are not continuous, causing storage space fragmentation.

Singly linked lists

template <typename DataType> struct Node{ DataType data; // Node<DataType> *next; // pointer field};Copy the code

Usually, a node of the same type is attached before the start node of a single linked list, called head node. After the head node is added, the head pointer always points to the head node regardless of whether the single linked list is empty or not, so the treatment of empty and non-empty tables becomes unified.

template <typename DataType> class LinkList{ public: LinkList(); LinkList(DataType a[],int n); // Create a single list with n elements ~LinkList(); // destructor int Length(); DataType Get(int I); Int Locate(DataType x); int Locate(DataType x); Void Insert(int I,DataType x); void Insert(int I,DataType x); DataType Delete(int I); DataType Delete(int I); // Delete the ith node bool Empty(); Void PrintList(); Private: Node<DataType> *first; // single list header pointer};Copy the code

1. No-parameter constructor

template <typename DataType> LinkList<DataType>::LinkList(){ first = new Node<DataType>; First ->next = nullptr; // the pointer field of the head node is null}Copy the code

2. Parameter constructors

(1) interpolation

If a[5]={1,2,3,4,5}, the traversal will print “5,4,3,2,1” after the headplug constructor.

template <typename DataType> LinkList<DataType>::LinkList(DataType a[],int n){ first = new Node<DataType>; first->next = nullptr; for (int i=0; i<n; i++){ Node<DataType> *s = nullptr; s= new Node<DataType>; s->data = a[i]; s->next = first->next; first->next = s; // Insert s into the head node}}Copy the code

(2) the tail insertion method

If a[5]={1,2,3,4,5}, the traversal will print “1,2,3,4,5” after the tail insert constructor.

template <typename DataType> LinkList<DataType>::LinkList(DataType a[],int n){ first = new Node<DataType>; Node<DataType> *r = first, *s = nullptr; For (int I =0; i<n; i++){ s = new Node<DataType>; s->data = a[i]; r->next = s; r = s; } r->next = nullptr; // Set the pointer field of the terminal node to null}Copy the code

destructors

template <typename DataType> LinkList<DataType>::~LinkList(){ Node<DataType> *p = first; while (first ! Nullptr){first = first->next; delete p; p = first; }}Copy the code

4. Find the length of a single list

template <typename DataType> int LinkList<DataType>::Length(){ Node<DataType> *p = first->next; Int count = 0; while (p ! = nullptr){ p = p->next; count++; } return count; }Copy the code

**O(n) **O(n)

template <typename DataType> DataType LinkList<DataType>::Get(int i){ Node<DataType> *p = first->next; Int count = 1; while (p! =nullptr && count<i){ p = p->next; count++; } if (p == nullptr) throw "illegal search location"; else return p->data; }Copy the code

**O(n) **O(n)

template <typename DataType> int LinkList<DataType>::Locate(DataType x){ Node<DataType> *p = first->next; Int count = 1; while (p ! = nullptr){ if (p->data == x) return count; p = p->next; count++; } return -1; // Exit loop surface lookup failed}Copy the code

Insert operation **O(n)

template <typename DataType> void LinkList<DataType>::Insert(int i,DataType x){ Node<DataType> *p = first, *s = nullptr;  int count = 0; while (p ! = nullptr && count < I - 1) {/ / find the first (I - 1) node p = p - > next; count++; } if(p == nullptr) throw "illegal insertion location"; Else {s = new Node<DataType>; s->data = x; S ->next = p->next; p->next = s; // Insert s after p}}Copy the code

**O(n)

template <typename DataType> DataType LinkList<DataType>::Delete(int i){ DataType x; Node<DataType> *p = first, *q = nullptr; int count = 0; while (p! = nullptr && count < I - 1) {/ / find the first (I - 1) node p = p - > next; count++; } if (p==nullptr || p->next==nullptr) throw "illegal deleted location"; else { q = p->next; x = q->data; P ->next = q->next; // delete q; return x; }}Copy the code

P ->next==nullptr; p->next==nullptr; Nullptr =nullptr =nullptr

9. Check whether the linear table is empty

template <typename DataType> bool LinkList<DataType>::Empty(){ return first->next==nullptr? true:false; }Copy the code

10. Traversal operation

template <typename DataType> void LinkList<DataType>::PrintList(){ Node<DataType> *p = first->next; While (p! = nullptr){ cout << p->data << "\t"; p = p->next; } cout << endl; }Copy the code

Double linked list

If you want to quickly determine the precursor of any node in a single linked list, you can set up a pointer field for each node in the single linked list to point to its precursor, thus forming a double Linked list. Like singly linked lists, double-linked lists are typically uniquely identified by header Pointers, and adding headers can also facilitate some operations on double-linked lists.

template <typename DataType> struct Node{ DataType data; Node<DataType> *prior,*next; // precursor, successor pointer field};Copy the code

The implementation of operations such as length, bitwise lookup, value lookup, and traversal in double-linked lists is basically the same as in single-linked lists. Insert and delete operations are discussed below.

1. Insert operations

Insert a new node S after node P, need to modify 4 Pointers:

(1) s – > the prior = p;

(2) s – > next = p – > next;

(3) p – > next – > the prior = s;

(4) p – > next = s;

When changing the pointer of ② and ③, p->next is used to find the successor node of node P, so the pointer of ④ can be changed only after the pointer of ② and ③ are changed.

2. Delete the vm

Let the pointer P point to the node to be deleted, and the deletion operation can be completed through the following three statements:

(1) p – > the prior – > next = p – > next;

(2) p – > next – > the prior = p – > the prior;

3. Delete p;

The order of the first two statements can be reversed.

Circular linked list

In a single linked list, if the pointer of the terminal node is changed from a null pointer to a head node, the whole single linked list will form a ring. Such head to tail single linked list is called circular singly Linked list. In a circular single linked list indicated by the head pointer, the time to find the starting node is O(1). However, the time to find the end node is O(n). If the tail pointer pointing to the end node is used to indicate the circular singly linked list, then the time to find the start node and the end node is O(1), and their storage addresses are rear->next->next and rear respectively, obviously the time is O(1). Therefore, the circular single – linked list indicated by tail pointer is used in practice.

Circular linked lists do not add any storage, only a slight change in the way linked lists are linked, so the implementation of basic operations is similar to linked lists. Starting from any node in the circular linked list, other nodes can be scanned to improve the flexibility of the linked list operation. But the danger of this approach is that the end of the cycle list without apparent, can lead to a circular linked list processing operations into an infinite loop, therefore, need to be pay attention to the loop condition, usually determine whether work as a loop variable pointer is equal to a specified pointer (e.g., head pointer or the tail pointer), to determine whether the work pointer to scan the entire circulation list. For example, the cyclic condition p! =first Determines whether the working pointer P scans the entire linked list.

A static linked list

Static lists use arrays to represent lists, and subscripts of array elements to simulate Pointers to lists. Because linked lists defined using arrays are static storage allocations, they are called static linked lists. The most commonly used static singly linked lists, in the case of not confuse, the static singly linked lists to static linked list, for short storage diagram as shown in the figure below, which is the avail free list spare array unit (all made of singly linked lists) head pointer, the head of the first is a static linked list pointer, convenient for operation, static pointer list also take the lead.

Each array element of a static list consists of two fields: the data field holds the data element, and the next field holds the array index of the element’s successors.

template <typename DataType> struct SNode{ DataType data; int next; // pointer field (also called cursor), note not pointer type};Copy the code

Static list implementation

const int MaxSize = 100; Template <typename DataType> class StaList{public: StaList(); // Initializes the empty static list and the free list StaList(DataType a[],int n); // create a list of length n ~StaList(); // Destructor // same as single list member function private: SNode SList[MaxSize]; // Static list array int first,avail; // cursor, linked header pointer and free header pointer};Copy the code

Static lists use static storage allocation, so the destructor is empty. Table length, bitwise lookup, value lookup, traversal and other operations are basically the same as single-linked lists. Insert and delete operations are discussed below.

1. Insert operation

When inserting into a static linked list, first remove a node from the front end of the free chain and insert the node into the static linked list. Assuming that the new node is inserted after node P, the operation of modifying the pointer is as follows:

s = avail; // No avail = SList[avail]. Next; // SList[s]. Data = x; SList[s].next = SList[p].next; SList[p]. Next = s; // SList[p].Copy the code

2. Delete operations

When deleting a node from a static linked list, first remove the node to be deleted from the static linked list and then insert it into the front end of the free chain. Assume that the successor node of node P needs to be deleted, then modify the pointer as follows:

q = SList[p].next; SList[p]. Next = SList[q]. Next; // SList[q]. Next = avail; // Insert node Q into the front end of avail = q; // Avail points to node QCopy the code

Static linked list summary:

Although static linked lists use arrays to store linear tables, only cursors need to be moved during insert and delete operations, and there is no need to move the elements in the table, thus improving the disadvantage of inserting and deleting a large number of elements in the sequential table.

Comparison of sequential and linked lists

Time performance comparison

1, if the linear table needs to be frequently searched but rarely insert and delete operations, or the operation is closely related to the “position of data elements in the linear table”, it is appropriate to use ** linear table ** as the storage structure;

2. If the linear table needs to be frequently inserted and deleted, the ** linked list ** should be used as the storage structure.

Space performance comparison

1. If the approximate length of a linear table is known in advance, the spatial efficiency of using a sequential table will be higher;

2. When the number of elements in a linear table changes greatly or is unknown, it is best to use ** linked list **.