Why do we use node * In linked list?

Linked List | Set 1 (Introduction)

Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.

Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have the following limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2) Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted but in Linked list if we have the head node then we can traverse to any node through it and insert new node at the required position.
For example, in a system, if we maintain a sorted list of IDs in an array id[].
id[] = [1000, 1010, 1050, 2000, 2040].
And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).
Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved due to this so much work is being done which affects the efficiency of the code.
Advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion
Drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node(head node). So we cannot do binary search with linked lists efficiently with its default implementation. Read about it here.
2) Extra memory space for a pointer is required with each element of the list.
3) Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.
Representation:
A linked list is represented by a pointer to the first node of the linked list. The first node is called the head. If the linked list is empty, then the value of the head points to NULL.
Each node in a list consists of at least two parts:
1) data(we can store integer, strings or any type of data).
2) Pointer (Or Reference) to the next node(connects one node to another)
In C, we can represent a node using structures. Below is an example of a linked list node with integer data.
In Java or C#, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

// A linked list node

struct Node {

int data;

struct Node* next;

};

C++

class Node {

public:

int data;

Node* next;

};

Java

class LinkedList {

Node head; // head of the list

/* Linked list Node*/

class Node {

int data;

Node next;

// Constructor to create a new node

// Next is by default initialized

// as null

Node(int d) { data = d; }

}
}

Python

# Node class

class Node:

# Function to initialize the node object

def __init__(self, data):

self.data = data # Assign data

self.next = None # Initialize

# next as null

# Linked List class

class LinkedList:

# Function to initialize the Linked

# List object

def __init__(self):

self.head = None

class LinkedList {

// The first node(head) of the linked list

// Will be an object of type Node (null by default)

Node head;

class Node {

int data;

Node next;

// Constructor to create a new node

Node(int d) { data = d; }

}
}

Javascript

<script>

var head; // head of the list
/* Linked list Node*/

class Node

{

// Constructor to create a new node

// Next is by default initialized

// as null

constructor(val) {

this.data = val;

this.next = null;

}

}
// This code is contributed by gauravrajput1
</script>

First Simple Linked List in C Let us create a simple linked list with 3 nodes.

C++

// A simple CPP program to introduce
// a linked list
#include <bits/stdc++.h>

using namespace std;

class Node {

public:

int data;

Node* next;
};
// Program to create a simple linked
// list with 3 nodes

int main()
{

Node* head = NULL;

Node* second = NULL;

Node* third = NULL;

// allocate 3 nodes in the heap

head = new Node();

second = new Node();

third = new Node();

/* Three blocks have been allocated dynamically.

We have pointers to these three blocks as head,

second and third

head second third

| | |

| | |

+---+-----+ +----+----+ +----+----+

| # | # | | # | # | | # | # |

+---+-----+ +----+----+ +----+----+

# represents any random value. 
Data is random because we haven’t assigned 
anything yet */

head->data = 1; // assign data in first node

head->next = second; // Link first node with

// the second node

/* data has been assigned to the data part of first

block (block pointed by the head). And next

pointer of the first block points to second.

So they both are linked.

head second third

| | |

| | |

+---+---+ +----+----+ +-----+----+

| 1 | o----->| # | # | | # | # |

+---+---+ +----+----+ +-----+----+
*/

// assign data to second node

second->data = 2;

// Link second node with the third node

second->next = third;

/* data has been assigned to the data part of the second

block (block pointed by second). And next

pointer of the second block points to the third

block. So all three blocks are linked.

head second third

| | |

| | |

+---+---+ +---+---+ +----+----+

| 1 | o----->| 2 | o-----> | # | # |

+---+---+ +---+---+ +----+----+ */

third->data = 3; // assign data to third node

third->next = NULL;

/* data has been assigned to the data part of the third

block (block pointed by third). And next pointer

of the third block is made NULL to indicate

that the linked list is terminated here.

We have the linked list ready.

head

|

|

+---+---+ +---+---+ +----+------+

| 1 | o----->| 2 | o-----> | 3 | NULL |

+---+---+ +---+---+ +----+------+

Note that only the head is sufficient to represent

the whole list. We can traverse the complete

list by following the next pointers. */

return 0;
}
// This code is contributed by rathbhupendra

// A simple C program to introduce
// a linked list
#include <stdio.h>

#include <stdlib.h>

struct Node {

int data;

struct Node* next;
};
// Program to create a simple linked
// list with 3 nodes

int main()
{

struct Node* head = NULL;

struct Node* second = NULL;

struct Node* third = NULL;

// allocate 3 nodes in the heap

head = (struct Node*)malloc(sizeof(struct Node));

second = (struct Node*)malloc(sizeof(struct Node));

third = (struct Node*)malloc(sizeof(struct Node));

/* Three blocks have been allocated dynamically.

We have pointers to these three blocks as head,

second and third

head second third

| | |

| | |

+---+-----+ +----+----+ +----+----+

| # | # | | # | # | | # | # |

+---+-----+ +----+----+ +----+----+

# represents any random value.

Data is random because we haven’t assigned

anything yet */

head->data = 1; // assign data in first node

head->next = second; // Link first node with

// the second node

/* data has been assigned to the data part of the first

block (block pointed by the head). And next

pointer of first block points to second.

So they both are linked.

head second third

| | |

| | |

+---+---+ +----+----+ +-----+----+

| 1 | o----->| # | # | | # | # |

+---+---+ +----+----+ +-----+----+

*/

// assign data to second node

second->data = 2;

// Link second node with the third node

second->next = third;

/* data has been assigned to the data part of the second

block (block pointed by second). And next

pointer of the second block points to the third

block. So all three blocks are linked.

head second third

| | |

| | |

+---+---+ +---+---+ +----+----+

| 1 | o----->| 2 | o-----> | # | # |

+---+---+ +---+---+ +----+----+ */

third->data = 3; // assign data to third node

third->next = NULL;

/* data has been assigned to data part of third

block (block pointed by third). And next pointer

of the third block is made NULL to indicate

that the linked list is terminated here.

We have the linked list ready.

head

|

|

+---+---+ +---+---+ +----+------+

| 1 | o----->| 2 | o-----> | 3 | NULL |

+---+---+ +---+---+ +----+------+

Note that only head is sufficient to represent

the whole list. We can traverse the complete

list by following next pointers. */

return 0;
}

Java

// A simple Java program to introduce a linked list

class LinkedList {

Node head; // head of list

/* Linked list Node. This inner class is made static so that

main() can access it */

static class Node {

int data;

Node next;

Node(int d)

{

data = d;

next = null;

} // Constructor

}

/* method to create a simple linked list with 3 nodes*/

public static void main(String[] args)

{

/* Start with the empty list. */

LinkedList llist = new LinkedList();

llist.head = new Node(1);

Node second = new Node(2);

Node third = new Node(3);

/* Three nodes have been allocated dynamically.

We have references to these three blocks as head,

second and third

llist.head second third

| | |

| | |

+----+------+ +----+------+ +----+------+

| 1 | null | | 2 | null | | 3 | null |

+----+------+ +----+------+ +----+------+ */

llist.head.next = second; // Link first node with the second node

/* Now next of the first Node refers to the second. So they

both are linked.

llist.head second third

| | |

| | |

+----+------+ +----+------+ +----+------+

| 1 | o-------->| 2 | null | | 3 | null |

+----+------+ +----+------+ +----+------+ */

second.next = third; // Link second node with the third node

/* Now next of the second Node refers to third. So all three

nodes are linked.

llist.head second third

| | |

| | |

+----+------+ +----+------+ +----+------+

| 1 | o-------->| 2 | o-------->| 3 | null |

+----+------+ +----+------+ +----+------+ */

}
}

Python

# A simple Python program to introduce a linked list
# Node class

class Node:

# Function to initialise the node object

def __init__(self, data):

self.data = data # Assign data

self.next = None # Initialize next as null
# Linked List class contains a Node object

class LinkedList:

# Function to initialize head

def __init__(self):

self.head = None
# Code execution starts here

if __name__=='__main__':

# Start with the empty list

llist = LinkedList()

llist.head = Node(1)

second = Node(2)

third = Node(3)

'''

Three nodes have been created.

We have references to these three blocks as head,

second and third

llist.head second third

| | |

| | |

+----+------+ +----+------+ +----+------+

| 1 | None | | 2 | None | | 3 | None |

+----+------+ +----+------+ +----+------+

'''

llist.head.next = second; # Link first node with second

'''

Now next of first Node refers to second. So they

both are linked.

llist.head second third

| | |

| | |

+----+------+ +----+------+ +----+------+

| 1 | o-------->| 2 | null | | 3 | null |

+----+------+ +----+------+ +----+------+

'''

second.next = third; # Link second node with the third node

'''

Now next of second Node refers to third. So all three

nodes are linked.

llist.head second third

| | |

| | |

+----+------+ +----+------+ +----+------+

| 1 | o-------->| 2 | o-------->| 3 | null |

+----+------+ +----+------+ +----+------+

'''

// A simple C# program to introduce a linked list

using System;

public class LinkedList {

Node head; // head of list

/* Linked list Node. This inner class is made static so that

main() can access it */

public class Node {

public int data;

public Node next;

public Node(int d)

{

data = d;

next = null;

} // Constructor

}

/* method to create a simple linked list with 3 nodes*/

public static void Main(String[] args)

{

/* Start with the empty list. */

LinkedList llist = new LinkedList();

llist.head = new Node(1);

Node second = new Node(2);

Node third = new Node(3);

/* Three nodes have been allocated dynamically.

We have references to these three blocks as head,

second and third

llist.head second third

| | |

| | |

+----+------+ +----+------+ +----+------+

| 1 | null | | 2 | null | | 3 | null |

+----+------+ +----+------+ +----+------+ */

llist.head.next = second; // Link first node with the second node

/* Now next of first Node refers to second. So they

both are linked.

llist.head second third

| | |

| | |

+----+------+ +----+------+ +----+------+

| 1 | o-------->| 2 | null | | 3 | null |

+----+------+ +----+------+ +----+------+ */

second.next = third; // Link second node with the third node

/* Now next of the second Node refers to third. So all three

nodes are linked.

llist.head second third

| | |

| | |

+----+------+ +----+------+ +----+------+

| 1 | o-------->| 2 | o-------->| 3 | null |

+----+------+ +----+------+ +----+------+ */

}
}
// This code has been contributed by 29AjayKumar

Linked List Traversal
In the previous program, we have created a simple linked list with three nodes. Let us traverse the created list and print the data of each node. For traversal, let us write a general-purpose function printList() that prints any given list.

Basic concepts and nomenclatureEdit

Each record of a linked list is often called an 'element' or 'node'.

The field of each node that contains the address of the next node is usually called the 'next link' or 'next pointer'. The remaining fields are known as the 'data', 'information', 'value', 'cargo', or 'payload' fields.

The 'head' of a list is its first node. The 'tail' of a list may refer either to the rest of the list after the head, or to the last node in the list. In Lisp and some derived languages, the next node may be called the 'cdr' (pronounced could-er) of the list, while the payload of the head node may be called the 'car'.

Singly linked listEdit

Singly linked lists contain nodes which have a data field as well as 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.

A singly linked list whose nodes contain two fields: an integer value and a link to the next node

The following code demonstrates how to add a new node with data "value" to the end of a singly linked list:

node addNode(node head, int value) { node temp, p; // declare two nodes temp and p temp = createNode(); // assume createNode creates a new node with data = 0 and next pointing to NULL. temp->data = value; // add element's value to data part of node if (head == NULL) { head = temp; // when linked list is empty } else { p = head; // assign head to p while (p->next != NULL) { p = p->next; // traverse the list until p is the last node. The last node always points to NULL. } p->next = temp; // Point the previous last node to the new node created. } return head; }

Doubly linked listEdit

In a 'doubly linked list', each node contains, besides the next-node link, a second link field pointing to the 'previous' node in the sequence. The two links may be called 'forward('s') and 'backwards', or 'next' and 'prev'('previous').

A doubly linked list whose nodes contain three fields: an integer value, the link forward to the next node, and the link backward to the previous node

A technique known as XOR-linking allows a doubly linked list to be implemented using a single link field in each node. However, this technique requires the ability to do bit operations on addresses, and therefore may not be available in some high-level languages.

Many modern operating systems use doubly linked lists to maintain references to active processes, threads, and other dynamic objects.[2] A common strategy for rootkits to evade detection is to unlink themselves from these lists.[3]

Multiply linked listEdit

In a 'multiply linked list', each node contains two or more link fields, each field being used to connect the same set of data records in a different order of same set (e.g., by name, by department, by date of birth, etc.). While doubly linked lists can be seen as special cases of multiply linked list, the fact that the two and more orders are opposite to each other leads to simpler and more efficient algorithms, so they are usually treated as a separate case.

Circular linked listEdit

In the last node of a list, the link field often contains a null reference, a special value is used to indicate the lack of further nodes. A less common convention is to make it point to the first node of the list; in that case, the list is said to be 'circular' or 'circularly linked'; otherwise, it is said to be 'open' or 'linear'. It is a list where the last pointer points to the first node.

In the case of a circular doubly linked list, the first node also points to the last node of the list.

Sentinel nodesEdit

In some implementations an extra 'sentinel' or 'dummy' node may be added before the first data record or after the last one. This convention simplifies and accelerates some list-handling algorithms, by ensuring that all links can be safely dereferenced and that every list (even one that contains no data elements) always has a "first" and "last" node.

Empty listsEdit

An empty list is a list that contains no data records. This is usually the same as saying that it has zero nodes. If sentinel nodes are being used, the list is usually said to be empty when it has only sentinel nodes.

Hash linkingEdit

The link fields need not be physically part of the nodes. If the data records are stored in an array and referenced by their indices, the link field may be stored in a separate array with the same indices as the data records.

List handlesEdit

Since a reference to the first node gives access to the whole list, that reference is often called the 'address', 'pointer', or 'handle' of the list. Algorithms that manipulate linked lists usually get such handles to the input lists and return the handles to the resulting lists. In fact, in the context of such algorithms, the word "list" often means "list handle". In some situations, however, it may be convenient to refer to a list by a handle that consists of two links, pointing to its first and last nodes.

Combining alternativesEdit

The alternatives listed above may be arbitrarily combined in almost every way, so one may have circular doubly linked lists without sentinels, circular singly linked lists with sentinels, etc.

TradeoffsEdit

As with most choices in computer programming and design, no method is well suited to all circumstances. A linked list data structure might work well in one case, but cause problems in another. This is a list of some of the common tradeoffs involving linked list structures.

Linked lists vs. dynamic arraysEdit

A dynamic array is a data structure that allocates all elements contiguously in memory, and keeps a count of the current number of elements. If the space reserved for the dynamic array is exceeded, it is reallocated and (possibly) copied, which is an expensive operation.

Linked lists have several advantages over dynamic arrays. Insertion or deletion of an element at a specific point of a list, assuming that we have indexed a pointer to the node (before the one to be removed, or before the insertion point) already, is a constant-time operation (otherwise without this reference it is O(n)), whereas insertion in a dynamic array at random locations will require moving half of the elements on average, and all the elements in the worst case. While one can "delete" an element from an array in constant time by somehow marking its slot as "vacant", this causes fragmentation that impedes the performance of iteration.

Moreover, arbitrarily many elements may be inserted into a linked list, limited only by the total memory available; while a dynamic array will eventually fill up its underlying array data structure and will have to reallocate—an expensive operation, one that may not even be possible if memory is fragmented, although the cost of reallocation can be averaged over insertions, and the cost of an insertion due to reallocation would still be amortized O(1). This helps with appending elements at the array's end, but inserting into (or removing from) middle positions still carries prohibitive costs due to data moving to maintain contiguity. An array from which many elements are removed may also have to be resized in order to avoid wasting too much space.

On the other hand, dynamic arrays (as well as fixed-size array data structures) allow constant-time random access, while linked lists allow only sequential access to elements. Singly linked lists, in fact, can be easily traversed in only one direction. This makes linked lists unsuitable for applications where it's useful to look up an element by its index quickly, such as heapsort. Sequential access on arrays and dynamic arrays is also faster than on linked lists on many machines, because they have optimal locality of reference and thus make good use of data caching.

Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items such as characters or boolean values, because the storage overhead for the links may exceed by a factor of two or more the size of the data. In contrast, a dynamic array requires only the space for the data itself (and a very small amount of control data).[note 1] It can also be slow, and with a naïve allocator, wasteful, to allocate memory separately for each new element, a problem generally solved using memory pools.

Some hybrid solutions try to combine the advantages of the two representations. Unrolled linked lists store several elements in each list node, increasing cache performance while decreasing memory overhead for references. CDR coding does both these as well, by replacing references with the actual data referenced, which extends off the end of the referencing record.

A good example that highlights the pros and cons of using dynamic arrays vs. linked lists is by implementing a program that resolves the Josephus problem. The Josephus problem is an election method that works by having a group of people stand in a circle. Starting at a predetermined person, one may count around the circle n times. Once the nth person is reached, one should remove them from the circle and have the members close the circle. The process is repeated until only one person is left. That person wins the election. This shows the strengths and weaknesses of a linked list vs. a dynamic array, because if the people are viewed as connected nodes in a circular linked list, then it shows how easily the linked list is able to delete nodes (as it only has to rearrange the links to the different nodes). However, the linked list will be poor at finding the next person to remove and will need to search through the list until it finds that person. A dynamic array, on the other hand, will be poor at deleting nodes (or elements) as it cannot remove one node without individually shifting all the elements up the list by one. However, it is exceptionally easy to find the nth person in the circle by directly referencing them by their position in the array.

The list ranking problem concerns the efficient conversion of a linked list representation into an array. Although trivial for a conventional computer, solving this problem by a parallel algorithm is complicated and has been the subject of much research.

A balanced tree has similar memory access patterns and space overhead to a linked list while permitting much more efficient indexing, taking O(log n) time instead of O(n) for a random access. However, insertion and deletion operations are more expensive due to the overhead of tree manipulations to maintain balance. Schemes exist for trees to automatically maintain themselves in a balanced state: AVL trees or red–black trees.

Singly linked linear lists vs. other listsEdit

While doubly linked and circular lists have advantages over singly linked linear lists, linear lists offer some advantages that make them preferable in some situations.

A singly linked linear list is a recursive data structure, because it contains a pointer to a smaller object of the same type. For that reason, many operations on singly linked linear lists (such as merging two lists, or enumerating the elements in reverse order) often have very simple recursive algorithms, much simpler than any solution using iterative commands. While those recursive solutions can be adapted for doubly linked and circularly linked lists, the procedures generally need extra arguments and more complicated base cases.

Linear singly linked lists also allow tail-sharing, the use of a common final portion of sub-list as the terminal portion of two different lists. In particular, if a new node is added at the beginning of a list, the former list remains available as the tail of the new one—a simple example of a persistent data structure. Again, this is not true with the other variants: a node may never belong to two different circular or doubly linked lists.

In particular, end-sentinel nodes can be shared among singly linked non-circular lists. The same end-sentinel node may be used for every such list. In Lisp, for example, every proper list ends with a link to a special node, denoted by nil or (), whose CAR and CDR links point to itself. Thus a Lisp procedure can safely take the CAR or CDR of any list.

The advantages of the fancy variants are often limited to the complexity of the algorithms, not in their efficiency. A circular list, in particular, can usually be emulated by a linear list together with two variables that point to the first and last nodes, at no extra cost.

Doubly linked vs. singly linkedEdit

Double-linked lists require more space per node (unless one uses XOR-linking), and their elementary operations are more expensive; but they are often easier to manipulate because they allow fast and easy sequential access to the list in both directions. In a doubly linked list, one can insert or delete a node in a constant number of operations given only that node's address. To do the same in a singly linked list, one must have the address of the pointer to that node, which is either the handle for the whole list (in case of the first node) or the link field in the previous node. Some algorithms require access in both directions. On the other hand, doubly linked lists do not allow tail-sharing and cannot be used as persistent data structures.

Circularly linked vs. linearly linkedEdit

A circularly linked list may be a natural option to represent arrays that are naturally circular, e.g. the corners of a polygon, a pool of buffers that are used and released in FIFO ("first in, first out") order, or a set of processes that should be time-shared in round-robin order. In these applications, a pointer to any node serves as a handle to the whole list.

With a circular list, a pointer to the last node gives easy access also to the first node, by following one link. Thus, in applications that require access to both ends of the list (e.g., in the implementation of a queue), a circular structure allows one to handle the structure by a single pointer, instead of two.

A circular list can be split into two circular lists, in constant time, by giving the addresses of the last node of each piece. The operation consists in swapping the contents of the link fields of those two nodes. Applying the same operation to any two nodes in two distinct lists joins the two list into one. This property greatly simplifies some algorithms and data structures, such as the quad-edge and face-edge.

The simplest representation for an empty circular list (when such a thing makes sense) is a null pointer, indicating that the list has no nodes. Without this choice, many algorithms have to test for this special case, and handle it separately. By contrast, the use of null to denote an empty linear list is more natural and often creates fewer special cases.

For some applications, it can be useful to use singly linked lists that can vary between being circular and being linear, or even circular with a linear initial segment. Algorithms for searching or otherwise operating on these have to take precautions to avoid accidentally entering an endless loop. One usual method is to have a second pointer walking the list at half or double the speed, and if both pointers meet at the same node, you know you found a cycle.

Using sentinel nodesEdit

Sentinel node may simplify certain list operations, by ensuring that the next or previous nodes exist for every element, and that even empty lists have at least one node. One may also use a sentinel node at the end of the list, with an appropriate data field, to eliminate some end-of-list tests. For example, when scanning the list looking for a node with a given value x, setting the sentinel's data field to x makes it unnecessary to test for end-of-list inside the loop. Another example is the merging two sorted lists: if their sentinels have data fields set to +∞, the choice of the next output node does not need special handling for empty lists.

However, sentinel nodes use up extra space (especially in applications that use many short lists), and they may complicate other operations (such as the creation of a new empty list).

However, if the circular list is used merely to simulate a linear list, one may avoid some of this complexity by adding a single sentinel node to every list, between the last and the first data nodes. With this convention, an empty list consists of the sentinel node alone, pointing to itself via the next-node link. The list handle should then be a pointer to the last data node, before the sentinel, if the list is not empty; or to the sentinel itself, if the list is empty.

The same trick can be used to simplify the handling of a doubly linked linear list, by turning it into a circular doubly linked list with a single sentinel node. However, in this case, the handle should be a single pointer to the dummy node itself.[8]

Beginner’s Guide to the Linked List Data Structure in Nodejs

Before you learn about the why, how, and when to use a linked list data structure for your project it is crucial to conceptualize how a linked list works.

What is a Linked List?

A linked list is a linear data structure stored randomly in memory and is made up of nodes that contain a value and a pointer.

So, a linked list is a linear data structure. This means that the data is “chained” one after the other in a linear fashion. Think of it like you are waiting in line; people exist one after another. When you approach a line you know who is first and last in line by identifying that there are no people behind/in front of them, while every other person has one in front and one behind. Similarly, a linked list or any other linear data structure keeps its data in order one after another.

You are probably thinking that a linked list is similar to an array. You would be right to make this assumption because they both use a linear data structure to organize data. But they are different because in a linked list the data is stored randomly in memory while the data in an array is stored together. For programmers, this means all of the data in an array can be accessed from a single reference in memory. In simpler terms, this means that the computer program only has to find the start of the array and it knows that for every x bytes (dependant on the data type) the next value will follow until it finds the end of the array. JavaScript knows by checking the length of the array when the array is declared. Linked lists do not use this strategy. Instead, when a linked list is called, JavaScript points to the head, and the rest of the data is scattered in memory, through the use of pointers within each node, the sum of data is still stored linearly.

Depiction of how arrays are stored in memory.

Depiction of how linked lists are stored in memory.

Let’s dive into what exactly is a node. As you know a node is a “container” which holds two pieces of data; a value and a pointer. A node is a custom data type that you must define for a linked list, and in the definition, you must include two variables: one for the value which can be any data type in JavaScript, and one for the pointer to the next node.

class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}

The code above is the blueprint for a node in JavaScript. When you create an instance of a Node you pass in the value and the node which follows it. Declaring a next method in the node allows you to create instances of Node whenever you want throughout the duration of your program. This also allows you to maintain a linear order as each node tells JavaScript where to look next, and when next is null, JavaScript will know that it has reached the end of the list. Earlier we thought of a linked list as a line, now we know that’s not accurate with how nodes are stored in memory. Instead, we can think of a linked list as a Take-A-Number system. This is a more accurate description of a linked list. The Take-A-Number system can be visualized as if you had walked into a waiting room and saw people waiting around in a scattered fashion; you grab a number and wait for your number to be called. As you see the next numbers pass, people stand up from different spots with no pattern. This is how a linked list is stored and used.

Why Should I Use a Linked List?

Here I am going to discuss what makes a linked list good and what makes it bad in comparison to the array data structure.

As developers, we judge the quality of a data structure based on three characteristics: the speed it takes to search, insert, and remove elements from it. More specifically, we calculate the Big O notation of each of the categories.

A linked list is best used when your task will frequently insert items from its list. For the insertion method, a linked list is O(1) in its worst case, which is as fast as possible. On the other hand, an array performs an insertion in O(n) in the best and worst-case scenarios. Arrays are statically declared, meaning that you get 1 shot to add everything you want and put it in the right order. Any time you want to add to it, the array must be remade so that all of the values can exist next to each other in memory.

Now if you have worked with arrays before, you know how fast it is to find a point of data with indexing O(1). Searching is the area where linked lists aren’t so great and if your task is going to do a lot of searching, you likely do not want to use it as your data structure. A linked list will have to start at the head (start) of the data and go to each Node until it finds what it’s looking for. At its best, a linked list will perform this in O(1). At its worst, it will have to check every Node and find what it’s looking for in the last one; performing the task in O(n). Both of these situations are very unlikely, with a 1/n chance of occurring for each of the two scenarios. The most common outcome will be somewhere in the middle of the data which would be around O(n/2) and rounded to O(n) … not great.

Lastly, there is the deletion method which is not a highlight for either of the two data structures. Linked Lists perform deletion in O(n) because it has to search through each Node one at a time which is the same reasoning as the searching method. Meanwhile, arrays also perform at O(n) as arrays need to be reformed every time as mentioned in the insertion paragraph. Linked lists aren’t great for deletion but are on par with array’s in this category so it should not be a reason to choose a linked list over an array.

Consider using a linked list data structure if you are going to perform many insertion tasks or if you will not be able to leverage the index search in an array.

How to Build a Linked List in Javascript

This guide will assume you have prior knowledge of object-oriented programming. Keep in mind that this will not be the only way to use and create a linked list; you may build it in a slightly different way or add more methods as you see fit.

The first step is to create a Node class as seen above.

class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}

Next, you need to create a LinkedList class.

class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
}

Here we are declaring the structure of a LinkedList and Node so that instances can be made from them. However instances of these two classes can’t work together yet, so let’s add more methods!

First, let’s allow for the creation of the first Node within the LinkedList class.

class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//Insert head aka first node
insertHead(data) {
this.head = new Node(data, this.head);
size++;
}
}
const ll = new LinkedList();
ll.insertHead(3);
console.log(ll) //Outputs: {head: Node {data: 100, next: null},
//size: 1}

Let’s break this down. I created a new method insertHead which creates an instance of Node within the LinkedList and assigns it to the head. When called we get an object which contains the head. The head is the Node we created with the value of 13 and no next since there was no head before the creation of this Node. Following the Node, we see the size which is 0 … odd? Nope, this is a class we made ourselves so we will have to remember to increment the size each time it grows.

Now if we were to continue with the code written here and call ll.insertHead(100) another time we would see.

{head: Node {data: 100, next: Node {data:13 next:null}}, size: 0}

The insertHead method properly makes the previous head become the next (pointer) to the newly created head.

Now you have to be saying “I’m sorry linked list you sound cool but you’re kind of ugly to read. How will I ever debug you?”. Well, that’s ok because we can fix that with a new method to only print the data of each node.

class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//Insert head aka first node
insertHead(data) {
this.head = new Node(data, this.head);
this.size++
}
//Pretty print of data
printData() {
let current = this.head;
while(current) {
console.log(current.data);
current = current.next;
}
}
}
ll.insertHead(2)
ll.insertHead(1)
ll.printData() //Outputs: 1,2

Now when we call the print data method we will only get the values. Much better.

Remember that the first and last nodes in a linked list are different from the rest. We already have the method for the first; let’s make the last.

//previous methods omitted for brevity
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//Make a Node at the end
insertLast(data) {
let last = new Node(data);
current = this.head;

while (current.next) {
current = current.next;
}
current.next = node;
this.size++;
}

In the insertLast method, we are creating a new Node and keeping it in the variable last. We then make a pointer to the head and create a while loop going through all of the next nodes like a chain while next is not null. When next is null we know we are at the end and then assign the currently last Node’s next method to point at the newly made node in the last variable.

Next is to show how to insert a Node at any other place in the linked list.

//previous methods omitted for brevity
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//Insert node at index
insertAt(data, index) {
const node = new Node(data);
let previous;
let current = this.head;
let count = 0;while(count < index) {
previous = current;
count++;
current = current.next;
}
node.next = current;
previous.next = node;
this.size++;
}
}

Depiction of what happens when the insertAt method is called

This one is where people get confused in linked lists so refer to the graphic above to make sense out of it as you read.

In the insertAt method, 2 parameters are taken but only the index is new. With the index, you can specify where in the linked list you want the new Node to be placed. First, we assign the new Node inside the node variable. We need to declare an empty previous variable. We have to start every search from the head of the linked list so we make a reference to the head and store it in the current variable. The last variable we need to make is count which is initialized to 0; this will be used to count up to the index argument.

Inside of the while loop, we are doing what you have seen before which is searching through the linked list. However, there is a difference, now we are incrementing count each loop and stopping after count is equal to the index argument. In the image above this is like searching until JavaScript finds the 3rd Node at index 2. When the loop is finished we will have the previous node in the variable previous and the node currently at the index, node needs to take in the variable current. We then replace the next connection between the previous (B in the graphic) and point it to node (E in the graphic). The linked list would end at node if we stopped here because it doesn’t point to anything. We then make the next of node point to next (C in the graphic).

There you go! We can now insert a new Node at any point in the linked list. Now all that’s left is to make a search and delete method.

//previous methods omitted for brevity
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
//return the data at index
search(index) {
let count = 0;
let current = this.head;
let foundData;

while(current) {
if (count === index) {
foundData = current.data;
}
count++;
current = current.next
}
return foundData;
}
}

Here I created a method to return the data at the index of the argument passed into the search method. You have seen a lot of it before so I will touch on what’s new. We are declaring an empty foundData variable and looping through the list until count is equal to the index argument then storing the data of the Node at that location inside the foundData variable. Then we simply return the foundData variable and that’s it! The rest are all things you have learned already.

Lastly, we need to be able to delete a Node from the linked list.

//previous methods omitted for brevity
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
//Remove at index
remove(index) {
let current = this.head;
let previous;
let count = 0;
if(index === 0) {
this.head = current.next;
} else {
while (count > index) {
count++;
previous = current;
current = current.next;
}
previous.next = current.next
}
this.size--;
}
}

By now you can probably understand what’s happening here. Everything in the code above is a mixture of other things you have learned. Here’s a quick recap of what’s going on.

The remove method can be called and passed an argument which will be the index of the Node to be deleted. If the index was 0 it needs to be handled differently because there isn’t a Node behind it. If the index is 0 we simply need to store the second Node inside of the head. That’s done, now what if it’s not the first? Then we loop through the list while count is less than the index argument. When the loop finishes we have the current + 1 inside current and previous Node’s. We then attach the two by changing the next of previous to point at current.

DONE! That’s all the basics of how to make and use a linked list. You will want to add more methods and build on the current methods as they are barebone and provide no error checking.

Doubly Linked Lists

Yes, there’s more. This will be quick to understand with all of your amazing knowledge on linked lists.

There is another type of linked list called a doubly linked list. It is much less common than a linked list, but it has its place. Its name is very fitting and it is the same thing as a regular linked list but it has 2 pointers (links) one forward and one back.

As you can see it looks the same. Except there are 2 pointers for each and 2 null’s one in the front and one in the back.

This type of linked list has a very niche use. You’ll find it useful when you are creating a feature that needs to undo and redo. Think of your web browser, it has a forward and previous button. This can be done with a doubly-linked list, but not a regular one. If you were to click on 3 websites, then go back 1 step, then go to another different one you wouldn’t be able to access the 3rd website through the forward and previous buttons. This is because the link has been broken and is now attached to the last website you went to. Similar to how we inserted a new Node except the next on the last website you visited is null since it is the most recent.

Linked lists

Introduction

Linked lists are the best and simplest example of a dynamic data structure that uses pointers for its implementation. However, understanding pointers is crucial to understanding how linked lists work, so if you've skipped the pointers tutorial, you should go back and redo it. You must also be familiar with dynamic memory allocation and structures.

Essentially, linked lists function as an array that can grow and shrink as needed, from any point in the array.

Linked lists have a few advantages over arrays:

Items can be added or removed from the middle of the list
There is no need to define an initial size

However, linked lists also have a few disadvantages:

There is no "random" access - it is impossible to reach the nth item in the array without first iterating over all items up until that item. This means we have to start from the beginning of the list and count how many times we advance in the list until we get to the desired item.
Dynamic memory allocation and pointers are required, which complicates the code and increases the risk of memory leaks and segment faults.
Linked lists have a much larger overhead over arrays, since linked list items are dynamically allocated (which is less efficient in memory usage) and each item in the list also must store an additional pointer.

What is a linked list?

A linked list is a set of dynamically allocated nodes, arranged in such a way that each node contains one value and one pointer. The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list.

A linked list is held using a local pointer variable which points to the first item of the list. If that pointer is also NULL, then the list is considered to be empty.

------------------------------ ------------------------------ | | | \ | | | | DATA | NEXT |--------------| DATA | NEXT | | | | / | | | ------------------------------ ------------------------------

Let's define a linked list node:

typedef struct node { int val; struct node * next; } node_t;

Notice that we are defining the struct in a recursive manner, which is possible in C. Let's name our node type node_t.

Now we can use the nodes. Let's create a local variable which points to the first item of the list (called head).

node_t * head = NULL; head = (node_t *) malloc(sizeof(node_t)); if (head == NULL) { return 1; } head->val = 1; head->next = NULL;

We've just created the first variable in the list. We must set the value, and the next item to be empty, if we want to finish populating the list. Notice that we should always check if malloc returned a NULL value or not.

To add a variable to the end of the list, we can just continue advancing to the next pointer:

node_t * head = NULL; head = (node_t *) malloc(sizeof(node_t)); head->val = 1; head->next = (node_t *) malloc(sizeof(node_t)); head->next->val = 2; head->next->next = NULL;

This can go on and on, but what we should actually do is advance to the last item of the list, until the next variable will be NULL.

Iterating over a list

Let's build a function that prints out all the items of a list. To do this, we need to use a current pointer that will keep track of the node we are currently printing. After printing the value of the node, we set the current pointer to the next node, and print again, until we've reached the end of the list (the next node is NULL).

void print_list(node_t * head) { node_t * current = head; while (current != NULL) { printf("%d\n", current->val); current = current->next; } }

Adding an item to the end of the list

To iterate over all the members of the linked list, we use a pointer called current. We set it to start from the head and then in each step, we advance the pointer to the next item in the list, until we reach the last item.

void push(node_t * head, int val) { node_t * current = head; while (current->next != NULL) { current = current->next; } /* now we can add a new variable */ current->next = (node_t *) malloc(sizeof(node_t)); current->next->val = val; current->next->next = NULL; }

The best use cases for linked lists are stacks and queues, which we will now implement:

Adding an item to the beginning of the list (pushing to the list)

To add to the beginning of the list, we will need to do the following:

Create a new item and set its value
Link the new item to point to the head of the list
Set the head of the list to be our new item

This will effectively create a new head to the list with a new value, and keep the rest of the list linked to it.

Since we use a function to do this operation, we want to be able to modify the head variable. To do this, we must pass a pointer to the pointer variable (a double pointer) so we will be able to modify the pointer itself.

void push(node_t ** head, int val) { node_t * new_node; new_node = (node_t *) malloc(sizeof(node_t)); new_node->val = val; new_node->next = *head; *head = new_node; }

Removing the first item (popping from the list)

To pop a variable, we will need to reverse this action:

Take the next item that the head points to and save it
Free the head item
Set the head to be the next item that we've stored on the side

Here is the code:

int pop(node_t ** head) { int retval = -1; node_t * next_node = NULL; if (*head == NULL) { return -1; } next_node = (*head)->next; retval = (*head)->val; free(*head); *head = next_node; return retval; }

Removing the last item of the list

Removing the last item from a list is very similar to adding it to the end of the list, but with one big exception - since we have to change one item before the last item, we actually have to look two items ahead and see if the next item is the last one in the list:

int remove_last(node_t * head) { int retval = 0; /* if there is only one item in the list, remove it */ if (head->next == NULL) { retval = head->val; free(head); return retval; } /* get to the second to last node in the list */ node_t * current = head; while (current->next->next != NULL) { current = current->next; } /* now current points to the second to last item of the list, so let's remove current->next */ retval = current->next->val; free(current->next); current->next = NULL; return retval; }

Removing a specific item

To remove a specific item from the list, either by its index from the beginning of the list or by its value, we will need to go over all the items, continuously looking ahead to find out if we've reached the node before the item we wish to remove. This is because we need to change the location to where the previous node points to as well.

Here is the algorithm:

Iterate to the node before the node we wish to delete
Save the node we wish to delete in a temporary pointer
Set the previous node's next pointer to point to the node after the node we wish to delete
Delete the node using the temporary pointer

There are a few edge cases we need to take care of, so make sure you understand the code.

int remove_by_index(node_t ** head, int n) { int i = 0; int retval = -1; node_t * current = *head; node_t * temp_node = NULL; if (n == 0) { return pop(head); } for (i = 0; i < n-1; i++) { if (current->next == NULL) { return -1; } current = current->next; } if (current->next == NULL) { return -1; } temp_node = current->next; retval = temp_node->val; current->next = temp_node->next; free(temp_node); return retval; }