Linked Lists

Linked Lists are a linear data structures consisting of nodes, each containing a value and a reference to the next node.

Unlike arrays, linked lists allow an efficient insertion and deletion. However, we cannot access elements by index, so we need to traverse the entire list to do so.

Operations

Let's check the complexity of linked lists' common operations:

Operation	Time Complexity	Space Complexity
Size	$O (1)$	$O (1)$
Get i-th	$O (n)$	$O (1)$
Set i-th	$O (n)$	$O (1)$
Copy	$O (n)$	$O (n)$
Append	$O (1)$	$O (1)$
Pop first	$O (1)$	$O (1)$
Pop last	$O (1)$	$O (1)$
Pop i-th	$O (n)$	$O (1)$
Delete value	$O (n)$	$O (1)$
Iterate	$O (n)$	$O (1)$
Search	$O (n)$	$O (1)$

Types

There are two kinds of Linked Lists:

Singly Linked Lists.
Doubly Linked Lists.

`collections.deque`

The deque module can also simulate a Linked List. You can find more information in the Queue paragraph.

algo-ds.com

Linked Lists

Operations

Types

collections.deque

`collections.deque`