List

Linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists

Time Complexity

action	time
Insertion	O(1)
Deletion	O(1)
Search	O(n)

Properties

• first
• last
• size

Methods

pushFront(value)

  Insert the node with a value in front of the list.

pushBack(value)

  Insert the node with a value in back of the list.

popFront()

  Delete the node in front of the list.

popBack()

  Delete the node in back of the list.

front()

  Return value of the node in front of the list.

back()

  Return value of the node in back of the list.

size()

  Return size of the list.

isEmpty()

  Check the list is empty.

clear()

  Clear the list.

at(index)

  Return the node located at the index of the list.

insert(index,value)

  Insert the node at the index position of the list.

delete(index)

  Delete the node located at the index of the list.

Example

Let's install @structure-js/datastructure npm-package.

npm i @structure-js/datastructure

If you have installed it, Let's create List and push some values.

let List = require('@structure-js/datastructure').List;

let list = new List();
list.pushFront(1);
list.pushFront(2);
list.pushFront(3);   
list.pushBack(4);

let str = "";
for(let num of list){
    str += num + "\t";
}
console.log(str);

console.log("list.at(2) : " + list.at(2));

result

3	2	1	4	
list.at(2) : 1

Then, It would be like this.

[Image 1]

Next, Let's delete a node with index 2.

list.delete(2);

str = "";
for(let num of list){
    str += num + "\t";
}
console.log(str);

result

3	2	4	

Then, It would be like this.

[Image 2]

Next, Let's insert 1 again at index 2.

list.insert(2, 1);

str = "";
for(let num of list){
    str += num + "\t";
}

result

3	2	1	4	

Then, It would be like this.

[Image 3]