The list

Linked lists are a kind of physics
Storage unitNot sequential or sequential
Storage structure.
The data elementThe logical order is through the linked list
Pointer to theLink order is implemented. A linked list consists of a series of nodes (each element in the list is called a node) that can be dynamically generated at run time. Each node consists of two parts: one is storage
The data elementThe other one stores the address of the next node
Pointer to theThe domain. [Source Baidu Encyclopedia]

List characteristics

  • Use an arbitrary set of memory Spaces to store data elements (here the memory Spaces can be contiguous or discontiguous).
  • Each node consists of the data itself and a pointer to the next node
  • Access to the entire list must start from the beginning, with the header pointer pointing to the first node
  • The pointer to the last node points to NULL

There is no pointer in JS. The pointer to the above node is just a borrowed C concept.

List complexity

Time complexity

Access Search Insertion Deletion
O(n) O(n) O(1) O(1)

Spatial complexity

O(n)

Unidirectional linked list implementation

Several major operations in a linked list

  • Initialize the linked list/node
  • Head insert node
  • Search/traverse nodes
  • Remove nodes
  • .

Initialize a node in a linked list

class LinkedListNode { constructor(value, next = null) { this.value = value; this.next = next; // Initialize to null}}

Initializing a unidirectional linked list

Class LinkedList {constructor() {this.head = null; }}

Append a node to the header (Append)

Const newNode = new LinkedListNode(value, this.head); // Assign a value to head for the next new creation this.head = newNode; }

Remove nodes

Delete (value) {// Return null if (! this.head) { return null; } // If the first node is deleted let deletedNode = null; While (this.head && this.head.value === value) {deletedNode = this.head; this.head = this.head.next; }} let currentNode = this.head; if (currentNode ! == null) { while (currentNode.next) { if (currentNode.next.value === value) { deletedNode = currentNode.next; currentNode.next = currentNode.next.next; } else { currentNode = currentNode.next; } } } return deletedNode; }

conclusion

Just to summarize, the simple idea of a linked list structure is that a node contains the current value and the next next. And then the initialization is a head. The same structure is appended in turn. It’s easy to understand, but of course there’s more to lists than that. There’s also two-way lists, operations like reverse, deleting (headers, tails), converting data structures, and so on.

See you next time.

Other links

The sample code repository above