Since I work on the front end, all of the code examples are written in TypeScript for a more user-friendly description of data structures.

1. Linear table types

  • 1. Sequential storage structure (array)
  • 2. Chained storage structure (linked list)

1.1. Sequential storage

A general exponential group in which the storage units of internal data are adjacent in memory

Advantages: Fast query, time complexity of O(1)

Disadvantage:

  1. Element increment and deletion operation time complexity is O(n)
  2. The length should be determined in advance
  1. Need to occupy continuous memory space

1.2. Chain storage

A finite sequence of n data elements, usually in chained form, is called a linear or linked list. The elements in a linked list are nodes, which are chunks of memory that store a single piece of data. A node usually consists of two parts:

  • Data stored on a node
  • Pointer to the next node

Take a look at the typescript implementation of linked lists

class ListNode { val: number next: ListNode | null constructor(val? : any, next? : ListNode | null) { this.val = val this.next = (next===undefined ? null : next) } }Copy the code

2. Linked list types

Linked list types are generally divided into the following:

  • Lead, don’t lead
  • One way, two way
  • Cyclic, acyclic

2.1 Taking the Lead and not taking the Lead

All linked lists have a header pointer. The header pointer of a leading node points to the header node, and the header pointer of a non-leading node points directly to the header node.

Primary node: The first node in a linked list used to store element nodes

Take the lead in:

Don’t take the lead in:

Operation difference: Delete and add operations, regardless of operation location, the linked list of the leading node does not need to modify the value of the head pointer, while non-leading nodes sometimes need to. In the purge operation, the headers of the leading nodes are preserved and those of the non-leading nodes are destroyed.

Structure difference: A headed list contains a head node regardless of whether the list is empty or not, while unheaded lists have no nodes.

The most commonly used linked list is the lead list

2.2. Bidirectional linked lists

In a single list, there is only one pointer to the next node; in a bidirectional list, there is one pointer to each node:

  • Pre: indicates the location of the previous node
  • Next: points to the next node location

Bidirectional linked list node diagram:

Bidirectional linked list node data structure:

class TwoWayListNode { val: number pre: ListNode | null next: ListNode | null constructor(val? : any, pre? : ListNode | null, next? : ListNode | null) { this.val = val this.next = (next===undefined ? null : next) } }Copy the code

Bidirectional linked list diagram:

// To implement the above structure, Const p1 = new TwoWayListNode('p1', null, null) const p2 = new TwoWayListNode('p2', null, const p2 = new TwoWayListNode('p2', null, null) const p3 = new TwoWayListNode('p3', null, null) p1.next = p2 p2.pre = p1 p2.next = P3Copy the code

2.3. Circular linked lists

The last node in the list points to the head node

// To implement the above structure, Const p1 = new ListNode('p1', null) const p2 = new ListNode('p2', null) const p3 = new ListNode('p3', null) p1.next = p2 p2.pre = p1 p2.next = P3 p3.next = p1Copy the code

And so on and so on and so on and so on and so on and so on and so on and so on and so on and so on and so on and so on and so on

3. Linear table data processing and analysis

3.1. Sequential storage operations

Query:

Since the sequential storage data is placed in a logical sequence into contiguous storage units, it is easy to implement query operations in the sequential table structure by directly fetching subscripts. Time complexity is O(1)

Insert:

In the sequential storage structure, the time complexity of the insertion tail is O(1) and the time complexity of the other locations is O(n).

If you want to insert a “six” at position 3, you need to move the “four” and “five” one unit back

Delete:

In the sequential storage structure, the time complexity of deleting the tail is O(1) and the time complexity of other locations is O(n).

To delete data “6 “, set the data in position 3 to null, and move the data in position” 4 “and” 5 “one unit in turn

3.2 Chain storage

Insert:

// p1 -> p2 -> p3 -> p4 
p1.next = p5
p5.next = p2
Copy the code

Delete:

// p1 -> p2 -> p3 -> p4 
p1.next = p3
p2.next = null
Copy the code

Query:

The search in the linked list can only start from the head pointer of the linked list and follow the linked pointer to search node by node until the desired result is found. Time complexity O(n)