Differences

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

 linked_list [2013/03/19 22:50]will linked_list [2015/02/02 08:28] (current) Both sides previous 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 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 ====== - A linked list is a data structure composed of a group of nodes which consist of two elements, data and a reference to the next node. + 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 ==== ==== Adding ==== - Adding creates ​a single ​node linked ​to the current first node, and changes ​the pointer ​to the first node to point to the new node. + 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 ==== ==== Removing ==== - If the first node is the node to remove, ​... + 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 - In progress... + 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. 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]