# Singly Linked Lists

## What is Linked lists?

Linked list **stores elements** in an **ordered sequence**. They are **made up of a lists of nodes** called **(ListNode)** This **ListNode** object contains two attributes:

- value - The
**node value**(exp: character, integer, object, etc) - next - It's actually a
**pointer**that**stores**the**reference**to the**next node**in the linked list.

ℹ️

Array are stored the same way in memory but linked list does not necessarily to store the same way in memory like array.

**Head** is the **1st node**, while **Tail** is the **last node**. Make sure you **adjust Head/Tail node** when **appending** a new node or **removing** the node.

Operation | Big-O Time | Notes |
---|---|---|

Access | O(n) | Have to loop to find the exact |

Search | O(n) | - |

Insert | O(1) | Reference to the node (position) |

Delete | O(1) | Reference to the node (position) |

```
class Node:
def __init__(self, val) -> None:
self.val = val
self.next = None
class LinkedList:
def __init__(self) -> None:
self.head = None
def get(self, index: int):
if self.head is None:
return -1
else:
i = 0
curr_node = self.head
while curr_node:
if i == index:
return curr_node.val
i += 1
curr_node = curr_node.next
def insert_head(self, val) -> None:
new_node = Node(val)
if self.head is None:
self.head = new_node
else:
new_node.next = self.head
self.head = new_node
def insert(self, val) -> None:
new_node = Node(val)
if self.head is None:
self.head = new_node
else:
curr_node = self.head
while curr_node.next:
curr_node = curr_node.next
curr_node.next = new_node
def remove(self, index: int):
curr_node = self.head
if index == 0 and curr_node:
self.head = curr_node.next
else:
i = 0
prev_node = None
while curr_node:
if i == index:
prev_node.next = curr_node.next
break
else:
i += 1
prev_node = curr_node
curr_node = curr_node.next
def display(self) -> list:
curr_node = self.head
res = []
while curr_node:
res.append(curr_node.val)
curr_node = curr_node.next
return res
```