User Tools

Site Tools


Differences

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

Link to this comparison view

Next revision
Previous revision
linked_list [2013/03/19 00:46]
will created
linked_list [2015/02/02 08:28] (current)
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 sequenceEach 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]
linked_list.1363679187.txt.gz · Last modified: 2015/02/02 08:24 (external edit)