The sea is wide by diving, the sky is high as birds fly. Hey how are you! I’m Ed Qin. 😄

You’ve seen the question “Why do you have lists when you already have arrays?”

In fact, linked lists and arrays have their own strengths and shine in different business scenarios. Many students may be familiar with and unfamiliar with linked lists. Familiar is that we often see the word “linked list” when we brush some eight-part essay. Strange is that we do not use the linked list too much in the usual development.

So let’s take a look at what a linked list is with the question, why do we need a linked list when we already have an array?

The concept of data structures?

Let’s break down some of the jargon that seems obscure:

Data: Corresponding to data types, js contains basic data types and reference data types

Structure: A collection of various data arranged and combined according to different logic and finally stored in computer memory

Conclusion: We call the various logical components of data, the storage structure in the computer and the algorithm design of various operations as data structure

The relationship between algorithms and data structures

Algorithm is based on data structure, the operation of data structure needs to be described by algorithm; Algorithm design depends on the logical structure of data, and algorithm implementation depends on the storage structure of data

  • Common data structures

Array, dictionary, linked list, stack, queue, hash table, binary tree, heap, hop table, graph, Trie tree

  • Common algorithms

Recursion, sorting, binary search, search, hash algorithm, greedy algorithm, divide-and-conquer algorithm, backtracking algorithm, dynamic programming, string matching algorithm, etc

What is an array structure

1. Array definition

An array is a collection of several elements arranged in order, and each element is identified by at least one index or key. The location of each element can be obtained by calculating the index

Why does every element have at least one index, because arrays can be multidimensional

But in our daily work, we usually use one-dimensional arrays, which can also be called linear arrays

One-dimensional array: [1,2,3]; / / an array of each element is a data type Two-dimensional array: [[" a ", "b", "c"], [1, 2, 3], 123]. / / an array of each element is a one dimensional array three-dimensional array: [[[" a ", "b", "c"], [1, 2, 3]], [[" a ", "b", "c"], [1, 2, 3]]]. // Each element of the array is a two-dimensional arrayCopy the code

2. Advantages and disadvantages of arrays

Array is one of the most common data structures in our work, and its biggest feature is efficient data query

However, its disadvantages are also very obvious. When inserting and deleting data, it takes a lot of time to move and fill bits

What is a linked list structure

1. Definition of linked list

A linked list structure is actually a storage method in memory. A linked list is a series of nodes connected in series, each node contains at least two parts: data field and pointer field

Data: Saves data

Pointer: A reference to the next node

Each node in the linked list forms a linear structure through the values of the pointer field

2. Pros and cons of linked lists

Because a list is a loose structure, when you want to find a node, you can only look down from the head node, but also because of this loose structure, it only needs to change the pointer field to insert and delete

Advantages: Suitable for dynamic insertion and deletion. Disadvantages: Cannot quickly locate and randomly access data

Array and linked list comparison summary

  • Arrays and linked lists are linear data structures
  • Arrays are static structures that allocate memory statically. Linked lists support dynamic memory allocation
  • An array is a contiguous memory space for data storage, while a linked list is discontiguous connected by Pointers
  • Arrays can be quickly searched by subscript location, while linked lists need to be searched by traversal
  • Arrays have a lot of data moving bits when they are inserted and deleted. Linked lists only need to change Pointers

Js linked list implementation

Different from new Array(), new Set(), new Map() and other data structures, js has not provided us with a direct API implementation of linked list. But we can simulate a linked list as an object

Linked lists can be divided into three categories:

  • One-way linked list: Linear data structure with pointer to next node and end point to NULL
  • Bidirectional linked lists: nodes can be added backwards or forwards, with Pointers to the previous and next nodes
  • Cyclic lists: The first node of a cyclic list points to the last node, and the last node points to the first node (cyclic lists can also be divided into one-way and two-way cyclic lists).

After objectifying the linked list, it looks like this

Const obj = {data: 1, next: {data: 2, next: {data: 3, next: null,},}; const obj = {data: 1, next: {data: 3, next: null,},};Copy the code

Insertion of linked lists

When we need to insert a node into a linked list, we just need to point the previous node to ourselves and point the current node to the next node

Deletion of linked lists

When we want to delete a node in the linked list, we just need to point the previous node of the target node to the next node of the current node, and point the target node to null to complete the release of a deletion operation

Implement a one-way linked list

class neNode { constructor(data) { this.data = data; this.next = null; }} class singleLinkedList {constructor() {this.head = null; } add(data) {let node = new neNode(data); if (this.head === null) { this.head = node; } else { let current = this.head; while (current.next) { current = current.next; } current.next = node; Insert (data, target) {let node = new neNode(data); let current = this.head; while (current.next) { if (current.data === target) { node.next = current.next; current.next = node; break; } current = current.next; }} find(data) {let current = this.head; while (current) { if (current.data === data) { return current; } current = current.next; } return null; } remove(data) {let current = this.head; let previous = null; while (current) { if (current.data === data) { if (previous === null) { this.head = current.next; } else { previous.next = current.next; } return true; } previous = current; current = current.next; } return false; } } const list = new singleLinkedList(); list.add(1); list.add(2); list.add(3); list.insert(4, 2); console.dir(list, { depth: null });Copy the code

The printed result is:

Thank you

Welcome to pay attention to my personal public number front Qin Aide every day to push you fresh quality good article. Reply “benefits” and you will get my carefully prepared front-end knowledge gift package. May you go all the way with light in your eyes!

Interested partners can also add my wechat: WebQinaid to exchange front-end technology and play together!

Phase to recommend

I developed a chrome plugin to remind you to drink water.

Come on! Talk with Ed Qin about “problems” at work

A perennial question, what is object orientation?