Linked List Data Structure

A data structure is a type of data that is organized in a certain way. One of the most basic and common types is the linked list, which is similar to the common array, but slightly different.

Linked List

A linked list is a collection of data elements (nodes) that each have a value, and something that points to the next element on the list. A list would consist of a head node that has points to another node via head.next, and that node would in turn point to another node, and so on until an end point of null. This is called a singly-linked list.

Example of a singly linked list. Each node contains data (A, B, C, D) and a next that points you to the next node.

There is also the doubly linked list, in which each node holds a value and a reference to the next node, but also a reference to the node before it. Here the previous node that the head points to is null, just like the end node’s next value.

Similar to a singly linked list, but nodes also reference the node prior to it.

And finally there is the circularly linked list, in which the end node points to the first node. A circularly linked list can be for both a doubly linked list or a singly linked list; for a singly linked list the “end node”’s next value would point at the head, and for a doubly linked list “end node”’s next value would point at the head and the “head node”’s previous value would point at the tail.

Example of a circularly singly linked list. The tail points at the head with its next value.

Example of a circularly doubly linked list. The tail points at the head with its next value, and the head points at the tail with its previous value.

Linked List vs Array

Pros

A linked list is somewhat similar to an array, but instead of each node having a set position via indexes, they all just follow each other but without a set position in space. This has some pros and cons, one of the pros being that it is easier to insert and remove values. For an array, to remove a value all the elements after it have to be shifted forward, and to insert a value all the elements after have to be shifted backwards. But for a linked list to insert or remove an element you just need to change the next value of the node before it (and for a doubly linked list also the previous value of the node after it). This will easily allow the nodes to connect to different nodes.

In this singly linked list the next value of the B node is simply swapped to point to node e instead of node c.

Cons

The fact that the linked list does not have a set position makes it harder to access an element (direct access). If you want the fourth element of an array, you can get it with array[3]. But for a linked list to get the fourth element, you must start at the head and go to the next value to get the next node 3 times. This makes it difficult to do things like get a random number.