User Tools

Site Tools


Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
linked_list [2013/03/19 22:50]
will
linked_list [2015/02/02 08:28] (current)
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 ​single ​node linked ​to the current first node, and changes ​the pointer ​to the first node to point to the new node.+To add 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)$ timeRemoving the node runs in $O(1)$ timeIf 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]
linked_list.1363758629.txt.gz · Last modified: 2015/02/02 08:24 (external edit)