# Differences

This shows you the differences between two versions of the page.

 linked_list [2013/03/19 00:46]will created linked_list [2015/02/02 08:28] (current) 2014/07/10 23:34 will 2014/05/04 16:25 external edit2013/03/22 19:27 will 2013/03/19 22:50 will 2013/03/19 00:46 will created Next revision Previous revision 2014/07/10 23:34 will 2014/05/04 16:25 external edit2013/03/22 19:27 will 2013/03/19 22:50 will 2013/03/19 00:46 will created Line 1: Line 1: - ====== Linked ​list ====== + ====== Linked ​List ====== - In progress... + A linked list is a data structure composed of a group of nodes, each node linking to the next node in the sequence. Each node consist of two elements, ''​.data''​ storing the contents of the node and ''​.next''​ a reference to the next node. + + Linked lists are one of the simplest data structures. They allow for efficient insertion or removal of elements from any position in the sequence. + + ==== Adding ==== + To add a new node with ''​data''​ to the start of a linked list: + - Create a new node containing ''​data''​ + - Point the ''​.next''​ of the new node to the current first node + - Point the start of the list to the new node + + This runs in $O(1)$ time. + + ==== Removing ==== + To remove data from a linked list: + - If the first node ''​.data''​ is equal to data: + - Point the start of the list to the node after the first node + - Otherwise:​ + - Find a node ''​prev''​ just before a node with ''​.data''​ equal to data + - Point ''​prev.next''​ to ''​prev.next.next''​ skipping the node being removed + + Finding the node to remove runs in $O(n)$ time. Removing the node runs in $O(1)$ time. If the previous node to the node to be removed is already available then removing the node always runs in $O(1)$ time. + + This visualisation allows the adding or removal of nodes to a linked list. Use the buttons on the right of the code to trigger running the commands on the list. [algorithm linked-list] [algorithm linked-list]