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;
}

This structure may change depending on the type of a linked list. The above structure is for Singly Linked List which contains a single pointer called next. This pointer is used to store the address of next node. In Doubly Linked List, however, one more pointer will be added called prev (the name can be anything but it’s a convention). This node stores the address of a previous node allowing backward traversals.

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

Linked lists are generally 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).