SinglyLinkedList.md (2030B)
1 # Singly Linked Lists 2 3 CS 221 W11 Lecture 13. 4 5 **Definition:** Singly linked lists are lists that only contain pointers to the next item in the list. This is in contrast with [DoublyLinkedList](DoublyLinkedList.md) which have a pointer forward and backward. 6 7 There is a pointer that needs to point to the head and then finding every subsequent element is as simple as iterating through the list. The final item in the list contains a null pointer. 8 9 Additionally, there are no cycles ([Graphs](Graphs.md)) in the list hence that makes them a "tree". 10 11 Inserting at the start is done as follows: 12 13 1. Create new node on the head (use the new keyword). 14 2. Point new node's pointer to the old start. 15 3. Point the head pointer (used to reference the list) to the new head 16 17 Removing first element (this is more complex in c/c++ because of memory management): 18 19 1. Create a pointer that will keep track of the node being removed 20 2. Point the head pointer to the next start 21 3. Deallocate the node that was removed in step 1. 22 23 Insert into arbitrary position: 24 25 1. Walk the list until reaching the point - 1 (done so insertion for position 3 is at 3 not 4) 26 2. Make new node 27 3. Create pointer that points to the next node in relation to the current node 28 3. Point the pointer on the current node to the newly created node 29 4. Point the pointer on the new node to the node that was previously referenced by the last node (tempPointer) 30 31 Removing arbitrary element: 32 33 1. Walk list until reaching the index -1 34 2. Create temp pointer with reference to the node that will be deleted 35 3. Point the current node's pointer to the pointer for the node after the deleted one 36 4. Deallocate the node marked for deletion 37 38 ## Efficiency Information: 39 40 Worst Case: 41 42 Add to end: O(n) 43 Remove from end: O(n) 44 Traverse to end: O(n) 45 46 These are worst case scenarios where you are searching, removing, and adding to the end of the list as it needs to be wholly traversed in such a case. 47 48 Best Case: 49 50 Add to start: O(1) 51 Remove from start: O(1) 52 Traverse to first: O(1) 53