What is a Linked List?

Linked list is a linear data structure where each element, called node, is connected via pointers. In other words, it’s a structure composed of group of nodes.

Here’s the pseudocode of a typical node in a linked list.

struct Node {
	T data;
	Node *next;
}

Linked list is a linear data structure where each element, called node, is connected via pointers. In other words, it’s a structure composed of group of nodes.

Here’s the pseudocode of a typical node in a linked list.

struct Node {
	T data;
	Node *next;
}

This structure may change depending on the type of a linked list. The above structure for example which is for [[Singly Linked List]] contains a single pointer called next. This pointer is used to store the address of a node next to the current node. In [[Doubly Linked List]], however, one more pointer will be added called prev. This node stores the address of a node in previous of the current one allowing backward traversals.

If backward traversal is necessary for your solution, it’s viable to use douly linked lists. Note that, it will consume more memory than a singly linked list due to extra pointer in the node.

Linked lists are genreally better off if lots of insertions and deletions are required because it can be done in constant time. If look-up operations are used more frequently, then it’d be better to use other data structures like a hash table or an array (Index operator is used for constant time look-up).