## Data Structures - Linked lists (Part 1/3)

This is the first part of a series of posts on DataStructures. The content of the posts is mainly from the “Technical Interview Practice” module in the Machine Learning Nanodegree (Udacity). I will include also the Quizzes (and their answers :-) ). The Quizzes were actually pretty good: proposing good examples for the implementation of the materials covered in the videos.

2. Stacks
3. Queues

Before we talk about Datastructures, we need to talk about code efficiency. The efficiency / Complexity of a code is estimated in term of:

• space-complexity: how much space the code requires, and

• time-complexity: how long the code takes to run

Those terms are typically estimated as a function of the length n of the input. The complexity is expressed as * O(n…)* (pronouce big-O)

Typically, we look at the worst case scenario when evaluating the complexity.

Ok! Now that we’ve got that out of the way, we will dive in and talk about our first data structure: linked lists.

A Linked list is not an array.

An array is a list with the following rules:

• each array element has an index (the element can be only numbers, characters, strings, or a mix):

• a drawback of arrays is that it is difficult to insert or delete elements

A linked list must have a head element, i.e the first element in the list. Each element only knows about the next element but that is all (next is a built-in iterator). Adding and removing element from a linked list is easier than for an array.

In the linked list, we store :

• the value: it can be a number or a character

• a reference to the next element in the list of the element

The advantage of Linked list is that removing and inserting elements can be done in constant time.

Double linked lists use pointers to the next element and to the previous element.

## Quizz

• get_position() returns the element at a certain position.
• insert() function will add an element to a particular spot in the list.
• delete() will delete the first element with that particular value.

class Element(object):
def __init__(self, value):
self.value = value #provide the value of the element
self.next = None #is a pointer to the next elemetn (memory location)

#if the linkedlist has a head, iterate thru next reference in every elemnt until you reach the end of the list do nothing

def append(self, new_element):
while current.next:
current = current.next
current.next = new_element
else:

def get_position(self, position):
"""Get an element from a particular position."""
i = 1

if position < 1:
return None

while current and counter <= position:
if i == position:
return current
current = current.next
i += 1
return None

def insert(self, new_element, position):
"""Insert a new node at the given position.
Assume the first position is "1".
Inserting at position 3 means between
the 2nd and 3rd elements."""
if position == 1:
else:
prev = self.get_position(position - 1)
next_element = prev.next
#assign new connections
prev.next = new_element
new_element.next = next_element

def delete(self, value):
"""Delete the first node with a given value."""
i = 1
while current.value != value and current.next:
current = current.next
i += 1
else:
prev = get_position(i)
prev.next = current.next.next

# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)

# Start setting up a LinkedList
ll.append(e2)
ll.append(e3)

# Test get_position
# Should print 3
# Should also print 3
print ll.get_position(3).value

# Test insert
ll.insert(e4,3)
# Should print 4 now
print ll.get_position(3).value

# Test delete
ll.delete(1)
# Should print 2 now
print ll.get_position(1).value
# Should print 4 now
print ll.get_position(2).value
# Should print 3 now
print ll.get_position(3).value