List-Based Collections - Linked Lists

Nov. 4, 2020

Vuong Huynh

Collection

A collection is a group of things. Collections don't have a particular order. Collections don't need the same type of objects.

There are many data structures extended from collections. They just add more rules to the ones that already applied for collections.

Lists

A list is a property of collections but the objects in a list have an order.

List (in Python) has no fixed length. We can add more objects anywhere within a list.

Arrays

The array is a list with added rules. Arrays have a set size that we determine when we create them.

Each array has a location called an index which is the number associated with that location in the array. The index starts at 0.

Delete or insert an element in an array is not simple.

List in Python is in fact built as an array. We can see inserting into a list is easy. However, inserting into an array is O(n), since we may need to shift elements to make space for the one we are inserting, or even copy everything to a new array if we run out of space. Thus, inserting into a Python list is actually O(n), while operations that search for an element at a particular spot are O(1).

The runtime of other list operations here. Learn more about Python Lists.

Linked Lists

A linked list is a chain of nodes (elements). Each node has a value and a pointer pointing (reference) to the next node.

The position of the first node (element) called header. The last node needs to point to Null.

In Python, however, there is no linked list in its standard library. We use the concept of linked list data structure to build linked lists in Python using Class. Because a linked list has some advantages compared to an array in Python such as:

more efficient in insert or delete
saves memory
nodes of linked lists can locate anywhere in the memory

However, the linear lookup time in a linked list will take O(n) while in an array is O(1)

Doubly Linked Lists are when we have pointers pointing to the next element as well as the previous element. This helps us to traverse both directions in the doubly linked list.

The efficiency of Linked List Operations (source)

Operation	Singly Linked List	Doubly Linked List
Access an element	O(n)	O(n)
Add/remove at an iterator position	O(1)	O(1)
Add/remove first element	O(1)	O(1)
Add last element	O(1)	O(1)
Remove last element	O(n)	O(1)

Implement a linked list using Class:

First, we need a Class named Element

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None

We use __init__ to initialize a new Element. An Element has some value associated with it (which could be anything—a number, a string, a character, et cetera), and it has a variable that points to the next element in the linked list.

Now, let's set up a LinkedList class:

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    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

The class LinkedList has a head Element, which is the first element in the list. If we establish a new LinkedList without a head, it will default to None.
Then, we add a method to our LinkedList to make it a little more useful. This method will add a new Element to the end of our LinkedList.

If the LinkedList already has a head, iterate through the next reference in every Element until we reach the end of the list. Set next for the end of the list to be the new_element. Alternatively, if there is no head already, we should just assign new_element to it and do nothing else.

Practice

The LinkedList code from before is provided below. Add three functions to the LinkedList.

get_position returns the element at a certain position.

The 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):
    """ class Element will hold value and pointer next to the next element """

    def __init__(self, value):
        self.value = value                  # declare value property
        self.next = None                    # property next is initialize None

class LinkedList(object):
    """ Initialine the header with None value in it """
    def __init__(self, head=None):
        self.head = head
        
    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):
        counter = 1
        current = self.head
        if position < 1:
            return None
        while current and counter <= position:
            if counter == position:
                return current
            current = current.next
            counter += 1
        return None
    
    def insert(self, new_element, position):
        counter = 1
        current = self.head
        if position > 1:
            while current and counter < position:
                if counter == position - 1:
                    new_element.next = current.next
                    current.next = new_element
                current = current.next
                counter += 1
        elif position == 1:
            new_element.next = self.head
            self.head = new_element
            
    def delete(self, value):
        current = self.head
        previous = None
        while current.value != value and current.next:
            previous = current
            current = current.next
        if current.value ==  value:
            if previous:
                previous.next = current.next
            else:
                self.head = current.next
    
# Test cases
# Set up some Elements - instantiate e1 to e5 with values 1 to 5
e1 = Element(1)         
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)
e5 = Element(5)

# Start setting up a LinkedList 
# Instantiate ll with LinkedList and pass object e1 into it and then append 
ll = LinkedList(e1)
ll.append(e2)
ll.append(e3)
ll.append(e4)
ll.append(e5)


print(ll.head.value)                        # 1 - print the header, which value is 1
print(ll.head.next.value)                   # 2 - next node has value of 2    
print(ll.head.next.next.value)              # 3 - and so on
print(ll.head.next.next.next.value)         # 4 - value of e4
print(ll.head.next.next.next.next.value)    # 5 - e5 value is appended

# Test position
# The Linked List now is 1, 2, 3, 4, 5
print(ll.get_position(3).value)             # 3 - the value of the node number 3

# Test insert
ll.insert(e5,3)                             # Insert the value of e5 (5) into position 3
# the Linked List now is 1, 2, 5, 3, 4, 5
print(ll.get_position(3).value)             # 4 - the value at position 3 is 4 now

# Test delete
ll.delete(1)                                # Delete the position 1 (header)
print(ll.get_position(1).value)             # 2 - value of header (1) has been deleted
# the Linked List now is 2, 5, 3, 4, 5
print(ll.get_position(2).value)             # 5 - position 3 (value of 5) become position 2
print(ll.get_position(3).value)             # 3 -