Linked list

A linked list is a simple data structure in which each object (or node) contains a link (or reference) to the next one in sequence. Such a list which linked both forwards and backwards is a doubly-linked list.

A node in a linked list typically contains the data required for the node, and a pointer to the next node in the list. In a doubly linked list, each node also contains a pointer to the previous node in the list.

An example structure for a linked list of int values in c would be:

struct linked_list_of_ints {

	int number;

	struct linked_list_of_ints * next;

};

Advantages and Disadvantages

Linked lists do not require continuous areas of memory. This avoids the need for resizing the allocated area of memory when the data set grows beyond the space initially allocated. When a new node is created, memory for that node is reserved, and the relevant pointers modified to add the node to the linked list.

Linked lists are a generally used for data sets which do not require random access, as finding a node in a linked list requires iterating over the list one element at a time until the required node is found.

Using Linked Lists

Adding and removing elements from a linked list is relatively straightforward:

To add an node to the end of the list, all that is required is to change the pointer in the last node to point to the new node.

To insert a new element into the middle of a linked list, the pointer in the new node is set to point to the node which will now follow it, and the pointer in the previous node is set to point to the new node.

To remove nodes from a linked list, the pointer in the previous node, is set to point to the node following the node(s) to be removed.

Linked list implementations

In low level programming languages with direct pointer manipulation capabilities such as c, programmers usually implement structures and methods to handle linked lists as needed. Higher level languages such as Java generally have a linked list implementation - or data structures based upon a linked list - and the methods required to add, remove, modify and iterate over nodes.