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.

  1. Linked lists
  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.

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.


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.

class Element(object):
    def __init__(self, value):
        self.value = value #provide the value of the element = 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:
                current =
   = new_element
            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 =
            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: = self.head
        	self.head = new_element
        	prev = self.get_position(position - 1)
        	next_element =
        	#assign new connections = new_element = 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 =
            i += 1
        if current == self.head:
            self.head =
            prev = get_position(i)
# 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)

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

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

# Test delete
# 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