Advantages, disadvantages and summary of sequence list and linked list

Catalog

One 、 The order sheet

The advantages of a sequence table ：

The disadvantages of the sequence table ：

Two 、 Linked list

Advantages of headless one-way acyclic linked list ：

Disadvantages of headless one-way acyclic linked list ：

Take the lead in two-way circular linked list ：

Take the lead in the disadvantages of two-way circular linked list ：

summary ：

---

There are mainly two basic storage structures in computers for storing linear tables ： Sequential and chain storage structures

One 、 The order sheet

The advantages of a sequence table ：

1、 The essence of a sequential table is an array , Physical space is continuous .

2、 Subscript random access .

3、 The efficiency of tail insertion and deletion is high , No need to move data , The time complexity is O(1).

4、cpu High cache hit rate .

The disadvantages of the sequence table ：

1、 When there is not enough space, the capacity needs to be expanded , Capacity expansion has certain performance consumption , Generally, it is capacity expansion 2 times , But there is also a certain waste of space

2、 It is inefficient to insert and delete in the head or in the middle , You need to move the data , The time complexity is 0(n).

Two 、 Linked list

Linked lists have many structures , In practice, the most commonly used are headless one-way acyclic list and leading two-way acyclic list .

Advantages of headless one-way acyclic linked list ：

1、 You can apply for and release space as needed , Don't worry about insufficient space .

2、 The insertion and deletion efficiency of the head and the middle position is high , No need to move data .

Disadvantages of headless one-way acyclic linked list ：

1、 Random access is not supported , Finding elements is inefficient .

2、 Insert and delete the middle or tail position of the linked list , You need to traverse nodes , The time complexity is 0(n).

Take the lead in two-way circular linked list ：

1、 You can apply for and release space as needed , Don't worry about insufficient space .

2、 The time complexity of inserting and deleting anywhere is 0(1).

Take the lead in the disadvantages of two-way circular linked list ：

1、 Subscript random access is not supported .

summary ：

1、 The essence of linked list is designed for the shortcomings of sequential list , Therefore, you can choose different storage structures in different situations

2、 If the main operation of a linear table is to find , Rarely do insert or delete operations , You can choose the sequence table as the storage structure .

3、 If the linear table needs to be inserted or deleted frequently , You can choose the linked list as the storage structure .

4、 Headless one-way acyclic linked lists are generally not used alone to store data , In fact, it is more as a substructure of other data structures , For example, hash bucket 、 The adjacency matrix of a graph .

5、 The leading two-way circular linked list is generally used to store data separately , It is also a commonly used linked list data structure in practice .