Linked List

Interface

Implement a linked linear list.

class Node(data: int | None = None)

The aotomic element of the linked list.

__init__(data: int | None = None) → None

Initialized the node of the linked list.

Variables:

• data – Stores the data of the node. It is None only when it is Sentinel Node or Dummy Node.

• next – Stores the point of the next node.

class LinkedList

Linear List implemented with linked list.

__init__() → None

Initialize an empty linked list begin with a sentinel node.

Variables:

head – A pointer to the sentinel node of the linkd list.

len() → int

Calculate the length of the given node.

Time complexity is \(O(n)\).

Returns:

Return the number of nodes int the linked list has, excluding the sentinel node.

index(index: int) → int

Find the value of the node at the given index.

Time complexity is \(O(n)\).

Parameters:

index – Specify the index of the node to be found.

Returns:

The value of the target node.

element(element: int, index: int = 0) → int

Find the index of the node that has the specifed element.

Time complexity is \(O(n)\).

Parameters:

• element – Specify the element to be found.

• index – Specify the index from which you want to start finding the node. Optional, defaults to 0 if not provided.

Returns:

The index of the first encountered node will be returned.

insert(element: int, index: int) → None

Insert the element into the linked list.

Time complexity is \(O(n)\).

Parameters:

• element – The element to be insert into the list.

• index – The position to be insert at in the list. The element would be inserted in the last of linked list if the given index out the right range of the list.

delete(index: int) → None

Delete the elemenet from the list.

Time complexity is \(O(n)\).

Parameters:

index – Specify the index at which the element is to be deleted.

class LinkedStack

Stack implemented with linked list.

__init__() → None

Initialize an empty linked stack.

Variables:

head – The pointer to the sentinel node.

push(item: int) → None

Push the given item to the top of the linked stack.

Variables:

item – The specified item to be pushd.

pop() → int

Pop the item from the top of the linked stack.

Returns:

The item at the top of the linked stack.

class LinkedQueue

Queue implemented with linked list.

__init__() → None

Initialize an empty queue.

Variables:

• front – Pointer to the front of the queue.

• rear – Pointer to the rear of the queue.

add(item: int) → None

Add the given item to the queue.

Parameters:

item – The item to be added.

delete() → int

Delete the item from the queue.

Returns:

The value to be deleted from the queue.