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.
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.
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
Double linked lists use pointers to the next element and to the previous element.
Quizz
Add/Complete the code for the three functions to the LinkedList:
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
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)
class LinkedList(object):
def __init__(self, head=None):
self.head = head
#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):
current = self.head
if self.head:
while current.next:
current = current.next
current.next = new_element
else:
self.head = new_element
def get_position(self, position):
"""Get an element from a particular position."""
i = 1
current = self.head
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:
new_element.next = self.head
self.head = new_element
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."""
current = self.head
i = 1
while current.value != value and current.next:
current = current.next
i += 1
if current == self.head:
self.head = current.next
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 = LinkedList(e1)
ll.append(e2)
ll.append(e3)
# Test get_position
# Should print 3
print ll.head.next.next.value
# 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