> See also: > -[[Data Structures]] > - https://www2.hawaii.edu/~esb/2011fall.ics211/sep14.html # Linked Lists ## Overview ## Types of Linked Lists - Basic - Head and Tail - Circular - Doubly Linked ![[Drawing 2023-03-30 02.13.11.excalidraw]] ![[Pasted image 20230227181024.png|400]] --- In a **singly (basic) linked list**, each element within the array will only have one pointer towards the next element in the array (or to NULL for the tail element). | Function | Runtime | | --- | --- | | `insertHead()` | $O(1)$ | | `removeHead()` | $O(1)$ | | `insertTail()` | $O(n)$ | | `removeTail()` | $O(n)$ | --- In a **doubly-linked list**, each element will contain a forward and backwards pointer towards the next and previous element within the structure. - Certain implementations have the previous pointer of the first element point to the final element and the next pointer of the final element will point towards the first element ```c struct Node { int data; Node * next; Node * prev; } ``` | Function | Runtime | | --- | --- | | `insertHead()` | $O(1)$ | | `removeHead()` | $O(1)$ | | `insertTail()` | $O(n)$ | | `removeTail()` | $O(n)$ | - [ ] Circular vs Non-Circular --- ## Abstract Data Types > See also: [[Data Structures#Abstract Data Types]] > [!note] Abstract Data Types > **Queue** > Removed oldest value in list (FIFO: "First In -> First Out") > > --- > **Stack** > Removes newest value in list > - Can be implemented with a basic linked list or even an ArrayList due to only interacting with one end of the data structure > - Examples: > - Used in the program stack (in C language) to handle function calls and ensuring that the most recent call is returned first > - Evaluating mathematical expressions (reverse polish notation/postfix notation)