## Intro

A linked list is a data structure which represents a sequence of nodes. In a singly linked list, each node points to the next node. In a doubly linked list, each node points to both the next and previous node.

To find nth element in the linked list, you have to iterate through n nodes which results in linear time complexity O(n). This is less efficient than array which has constant time complexity O(1) to access an element.

However, the advantage to use linked list is for insert and delete operation since it can be achieved in the constant time without shifting nodes around.

The following are the key methods to be implemented:

• remove(): remove a specified item from the linked list
• insertAt(index): insert an item at a given index
• deleteAt(index): delete an item at a given index
• find(): search an item in the linked list
• is_empty(): return if the linked list is empty or not
• count(): return the number of items in the linked list

## Construct a node class

Before we implement a singly linked list, we need to construct a node class. The linked list would contain one or more nodes. Each node has a value and a pointer linked to the next node.

``````class Node:
def __init__(self):
self.val = None
self.next = None

def set_val(self, val):
self.val = val

def get_val(self):
return self.val

def set_next(self, next):
self.next = next

def get_next(self):
return self.next
``````

## Build a singly Linked List

The first function in the linked list class is the constructor, which will be called whenever a linked list is initialized.

It can include three attributes:

• tail: the last node in the linked list
• count: the number of nodes in the linked list

Then we can build the other required functions according to the node pointer manipulations.

``````class LinkedList:
def __init__(self):
self.tail = None
self.count = 0

def count_nodes(self):
return self.count

# insert at the tail of list
def insert(self, val):
new_node = Node()
new_node.set_val(val)

self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node

self.count += 1

# insert at the given index
def insertAt(self, val, index):
new_node = Node()
new_node.set_val(val)

current_idx = 0
previous_node = current_node

while current_idx < index and current_node.next != None:
previous_node = current_node
current_node = current_node.next
current_idx += 1

if current_idx == index:
# found the index
new_node.next = current_node
previous_node.next = new_node

# increase counter
self.count += 1
else:
print("the specified index {} is invalid".format(index))

# delete the specified node
def deleteAt(self, index):
current_idx = 0
previous_node = current_node

while True:
if current_idx < index:
if current_node.next != None:
# move on to the next node
previous_node = current_node
current_node = current_node.next
current_idx += 1
else:
print("invalid index {}".format(index))
break
else:
# found the index, delete it
if current_node.next == None:
# this is tail
previous_node.next = None
self.tail = previous_node
else:
# this is not tail
previous_node.next = current_node.next

# decrease the counter
self.count -= 1

break

def find(self, index):
current_idx = 0

while current_node.next != None:
if current_idx == index:
return current_node.get_val()
else:
current_node = current_node.next

print("invalid index {}".format(index))

def print_list(self):
current_idx = 0

while current_node.next != None:
print(current_node.get_val())
current_node = current_node.next

# print the last node
print(current_node.get_val())
print("count: {}".format(self.count_nodes()))
print()
``````

## Test the Linked List class

``````ll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(5)
ll.print_list()

ll.insertAt(4, 2)
ll.print_list()

ll.insertAt(3, 3)
ll.print_list()

ll.deleteAt(3)
ll.print_list()
``````

Output:

``````1
2
5
count: 3

1
2
4
5
count: 4

1
2
4
3
5
count: 5

1
2
4
5
count: 4
``````