Data Structures - Linked Lists (1.4.2)

This post covers the following topics:

• Linked Lists

Linked Lists

Linked lists are the most common type of dynamic data structure, as they are dynamic they can grow to any size that is required. Their size isn't declared at the beginning on the program.

Linked lists are made up of nodes and pointers, each node stores the pointer to the next node, this makes them extremely flexible and powerful data structured. They can implement all types of data stores.

Here's an example of a linked list:

Address	Node	Pointer
01	Perfume - Pale Waves	10
02	On Fire - Louis Tomlinson	03
03	Lemonade - Louis Tomlinson	07
04	Dark To Light - Louis Tomlinson	13
05	The Observer - Louis Tomlinson	04
06	Chicago - Louis Tomlinson	09
07	Sunflower - Louis Tomlinson	06
08
09	Lucid - Louis Tomlinson	05
10	Eighteen - Pale Waves	02
11
12
13	Little More Time - Niall Horan	0

Here's an implementation of a Linked List:

class Node
{
public:
	Node( string dataInput, Node* next=NULL);
	void setData( string dataValue);
	void setNext( Node* nextNode );
private:
	string data;
	Node* next;
};
Each nod

Adding an item

To add an item to a linked list all you have to do is create a node, then update the last item and set it's pointer to the new item that's been created.

Inserting an item

To insert an item, create a new node then work out the node that would come before it, set the new nodes pointer to previous nodes pointer value then set the previous nodes pointer to the new node.

Removing an item

To remove an item the pointer of the item pointing at the item being deleted needs to have it's pointer set to the pointer of the item being deleted. Then the item can be removed safely.

There are reasons to use a linked list over an array WHEN:

• You need real-time insertions and deletions (as a LinkedList is much faster than an array, ArrayList, list, etc.)

• You don't know the size of the list (arrays will have to be re-declared to grow)

• You don't need random access to any elements

• You want to be able to insert items at any position within the list (e.g. in a priority queue, like when people have a numbered wristband and re-join a queue in a position at a venue)

However an array would be better than a linked list WHEN:

• You need indexed and random access to elements

• You know the number of items in the array ahead of time

• You need speed when iterating through all the items in sequence.

• Memory is a concern as a LinkedList takes up more as they need to store pointers too, whereas arrays don't.