Singly Linked Lists

What is Linked lists?

ListNode

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.

ListNode2

ℹ️

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

Stack Queue