The difference between arrays and linked lists

Arrays occupy contiguous memory space in memory and traversal accesses corresponding elements by index

The linked list is scattered in memory, with a data field val and a pointer field next, which stores the memory address of the next successor node. The traversal starts at the start node and accesses next one by one.

1. Create linked lists

Creates the object with the constructor, val, and assigns the pointer to null

function ListNode(val) {
    this.val = val
    this.next = null
}

const node1 = new ListNode(1)
const node2 = new ListNode(2)
node1.next = node2
Copy the code

2. Add elements to the middle of the list

For example, node1 -> node2 above 1, now you want to insert node3 in the middle to form node1 -> node3 -> node2

const node3 = new ListNode(3)
node3.next = node1.next
node1.next = node3
Copy the code

3. Delete elements from linked lists

Using node1 -> node3 -> node2 from 2 above, now you want to remove the element node3

node1.next = node1.next.next
node1.next.next = null
Copy the code

As can be seen from the above, deleting the target node really needs to locate the precursor node of the target node

2. Array in JS

1. If the basic data type is defined in the array, it occupies a contiguous chunk of memory 2. If objects are defined in an array, they are not contiguous in memory, and the underlying allocation of memory is based on a hash map, implemented by a linked list of objects

1. Access the linked list

Let’s say you want to access the 10th element

// In a normal array: arr[9]In the listlet node = head
for (let i = 0; i < index && node; i ++){
    node = node.next)
}
Copy the code