# Linked Lists

Linked Lists are among the most common data structures used in computer science.

In arrays, the data is stored at contiguous memory locations but linked lists are different, they do not store data at contiguous memory locations. For each linked list node, it stores the value of the item and the reference (pointer) to the next item.

## Singly Linked Lists

Linked lists are dynamic data structures which means memory allocation is dynamic, reserved memory for linked list can increase or decrease at runtime and no memory is allocated in advance. Whenever a new memory space is needed for adding a new node to a linked list, the memory needed for the new node is created at runtime.

This dynamic memory allocation structure is also make easy updates possible. *Removing* and *inserting* nodes are **fast** operations in linked lists.

However, this kind of flexibility comes together with some trade-offs. Since each linked list node has to store the reference to the next node, some extra memory is required. Also, unlike arrays, where you can directly access an item with its index number, you cannot access a linked list item directly since only information you have is the first item in the linked list and references following to this first item. That is why, worst-case access time is **O(n)**.

## Doubly Linked Lists

Doubly Linked Lists are actually an extension to Singly Linked Lists with some advantages. Unlike singly linked lists, doubly linked lists can be searched and traversed from both directions because each node in a doubly linked list contains both next node link and previous node link which we can call *next and *prev*.

Also, basic operations like insertion or deletion are easier to implement in doubly linked lists because extra traverse operations to the previous node to store its value is unnecessary since referance to previous node is already stored in the node itself. Only drawbacks we can list are you need more memory space to store previous node reference for each node and these adds a few more steps to implementation.

## Implementation of a Singly Linked List

### Creating a Node

First of all, we need to define a **Node** class. I want to implement a Singly Linked List therefore, our node class will consists of two variables **val** for storing the *value* and **next** for storing the *reference to the next node*.

```
class Node:
def __init__(self, data):
"""
a node in a singly linked list.
"""
self.val = data
self.next = None
```

Value (`val`

) of the item will be set to the value passed by the constructor and the initial value of the `next`

node reference will be `None`

initially.

### Creating an Empty Singly Linked List

Lets create a singly linked list together. To be able to have a flexible implementation, I want to have `head`

, `tail`

and `size`

attributes in my singly linked list.

```
class LinkedList:
def __init__(self):
# create a new singly linked list
# takes O(1) time
self.head = None
self.tail = None
self.size = 0
```

Our empty linked list is ready. To initialize it, we need to call it like: `LinkedList()`

.

### Insert a New Node at the Beginning

We will add a `prepend()`

method to our existing singly linked list implementation which takes `data`

as a parameter and adds a new node at the beginning of the linked list with this `data`

.

```
def prepend(self, data):
# insert a new node at the beginning of the linked list
# takes O(1) time
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
new_node = Node(data)
new_node.next = self.head
self.head = new_node
self.size += 1
```

If our linked list is empty, `self.head`

will be `None`

and in this case, we are creating a new node and assign it to `self.head`

. Since there is only one node in the linked list, both `head`

and `tail`

are equal to this node.

If there are already some nodes in the linked list and we are just adding one more at the beginning of it, then we need to create a new node. `next`

attribute of this new node should refer to current `self.head`

. Also new `self.head`

will be this new node and old head became the second node in the linked list.

### Insert a New Node at the End

We need to implement an `append()`

method to our existing singly linked list implementation which takes `data`

as a parameter and adds a new node at the end of the linked list with this new `data`

.

```
def append(self, data):
# inserts a new node at the end of the linked list
# takes O(1) time
if self.head is None:
self.head = Node(data)
self.tail = self.head
else:
new_node = Node(data)
self.tail.next = new_node
self.tail = new_node
self.size += 1
```

If our linked list is empty, `self.head`

will be `None`

and in this case, we are creating a new node and assign it to `self.head`

. Since there is only one node in the linked list, both `head`

and `tail`

are equal to this node.

If there are already some nodes in the linked list and we are just adding one more at the end of it, then we need to create a new node and set this new node as `tail`

.

### Accessing a Node

To be able to access a specific node, you need to implement a `get()`

method which will get `index`

parameter.

```
def get(self, index):
# get the value of index-th node in the linked list
# return None if node not found
# takes O(n) time
if index < 0 or self.head is None or index >= self.size:
return None
if self.head is None:
return None
current = self.head
for i in range(index):
current = current.next
return current.val
```

You have to visit each node one-by-one until you reach the target `index`

value. This visiting process makes our time complexity **O(n)**.

### Insert a New Node at the Index

If we want to add our newly created node to an index, we need to create a new method `add_at_index()`

which takes `index`

and `data`

parameters.

```
def add_at_index(self, index, data):
# insert a new node at the index-th node of the linked list
# takes O(n) time
if index < 0 or index > self.size:
return print(f"index {index} is out of boundaries")
elif index == self.size:
self.append(data)
else:
current = self.head
for i in range(index - 1):
current = current.next
new_node = Node(data)
new_node.next = current.next
current.next = new_node
self.size += 1
```

To be able to insert a new node to an index, first you need to go to target place by visiting each node one-by-one. Then, updating `next`

parameter of previous node and newly created node will be necessary.

### Delete a Node at the Index

Just like Insert a New Node at the Index, to be able to delete *index-th* node, first you need to visit each node one-by-one until you reach the target node.

```
def delete_at_index(self, index):
# delete the index-th node of the linked list
# takes O(n) time
if index < 0 or index >= self.size:
return print(f"index {index} is out of boundaries")
elif index == 0:
self.head = self.head.next
if not self.head:
self.tail = None
else:
current = self.head
for i in range(index - 1):
current = current.next
if current.next.next is None:
current.next = None
self.tail = current
else:
current.next = current.next.next
self.size -= 1
```

After reaching to target, all you need to do is breaking the linked list links by setting the taret node to its next node.

## Summary

This post was all about Linked Lists and its implementation in Python 3.

Linked Lists are one of the most common data structures in Computer Science and has some great advantages with **O(1)** `prepend()`

/ `append()`

(to the beginning and end of the list). But directly accessing a node `get()`

or deleting a node `delete-at-index()`

is taking **O(n)** time.