Introduction

Just like arrays, Linked Lists are also used to store a collection of same type of data. Data type can be as simple as a primtive integer to a complex class object. However the structure of these two data structures is very different.

What is a Linked List?

A linked list consists of nodes, that are linked together like a chain. Each node holds data, along with a pointer to the next node. It may be singly linked, meaning it can only be traversed in one direction, or it can be doubly linked, meaning it can be traversed in both directions.

Basic operations in a linked list are insertion, search and deletion.

Linked Lists can be used to implement hashmaps, file systems, adjacency lists etc, for dynamic memory allocation, to perform arithmetic operations on long integers, for maintaining a directory of names etc.

Array vs. Linked Lists

Arrays and Linked Lists differ in the way they are allocated memory, how elements are inserted or deleted and also how elements are searched.

Memory Allocation

Arrays instantiate a whole block of memory per element at once, even if it does not contain any elements yet. For example array[10], will reserve 10 memory spaces, as soon as it is declared. Linked Lists are more dynamic in nature and they only reseve the memory as and when the need arises.

Insertion or Deletion

When it comes to insertion or deletion, linked lists only take 1 unit of time, as we just need to change the pointers. For Arrays however, it takes n units of time as we have to shift each array element left or right after the operation.

Searching

While searching for an element, linked lists are slower, because we only have access to the head node. We need to traverse the whole linked list, element by element, looking for the element to be searched. For arrays, it just takes 1 unit of time as the indices for each value are known.

What is a Node?

A Node is a basic building block of a linked list. It stores the data along with a pointer to the next node (like a link in a chain). It can store data types ranging from primitive values to a class object.

Singly Linked List

Signly Linked List consists of a chain of nodes, each node holding a pointer to only the next node (and not the previous node). This means a singly linked list can only be traversed in one direction. To access the linked list, we only need pointer to the head node. Below is a simple implementation:

(is_empty() method is used to check if the list is an empty list)

Node Implementation for an SLL:

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

SLL Implementation

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

    def is_empty(self):
        if self.head is None:
            return True

Insertion in an SLL

There are 3 ways to insert a value in a linked list:

Insert at Head
Insert at End
Insert After

Deleting in an SLL

There are 3 ways to delete a node from a linked list

Delete at Head
Delete at End
Delete by Value

Full SLL Implementation

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


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

    def is_empty(self):
        if self.head is None:
            return True

    def insert_at_head(self, data):
        if self.is_empty():
            self.head = Node()
            self.head.value = data
            return

        new = Node()
        new.value = data
        new.next = self.head

        self.head = new

    def insert_at_end(self, data):
        if self.is_empty():
            self.insert_at_head(data)
            return

        new = Node()
        new.value = data
        new.next = None

        last = self.head
        while last.next is not None:
            last = last.next

        last.next = new

    def insert_after(self, prev, data):
        if self.is_empty():
            self.insert_at_head(data)
            return

        new = Node()
        new.value = data

        current = self.head

        while current.next is not None and current.value is not prev:
            current = current.next

        if current is not None:
            new.next = current.next
            current.next = new

    def search_node(self, data):
        if self.is_empty():
            return False

        current = self.head
        while current.next is not None:
            if current.value is data:
                return True
            current = current.next

        return False

    def delete_at_head(self):
        if self.is_empty():
            return

        current = self.head
        self.head = current.next

    def delete_at_end(self):
        if self.is_empty():
            return

        current = self.head
        prev = None
        while current.next is not None:
            prev = current
            current = current.next

        prev.next = None

    def delete_by_value(self, data):
        if self.is_empty():
            return

        current = self.head
        prev = None

        if current.value is data:
            self.delete_at_head()
            return

        while current.next is not None:
            if current.value is data:
                prev.next = current.next
                return
            prev = current
            current = current.next

        print("can't delete, value not found")

    def print_list(self):
        if self.is_empty():
            print("list is empty")
            return

        pretty_list = self.prettify()
        print(pretty_list)

    def prettify(self):
        start_tag = "[H] "
        end_tag = "None"
        printer = ""

        printer += start_tag
        current = self.head
        while current is not None:
            printer += str(current.value)
            current = current.next

            printer += " -> "

        printer += end_tag

        return printer

Validating the SLL implementation

import educative.course1.linkedlists.singly_linked_list as sll


def main():
    example = sll.SinglyLinkedList()

    # inserting at head
    print("inserting at head...")
    example.insert_at_head(5)
    example.insert_at_head(6)
    example.insert_at_head(7)
    example.insert_at_head(8)

    # inserting at end
    print("inserting at end...")
    example.insert_at_end(10)
    example.insert_at_end(9)

    # inserting after a node
    print("inserting after...")
    example.insert_after(6, 12)
    example.insert_after(7, 14)
    example.insert_after(10, 20)

    # printing list
    example.print_list()

    # deleting at head
    print("deleting at head...")
    example.delete_at_head()
    example.print_list()

    # deleting by value
    print("deleting by value...")
    example.delete_by_value(12)
    example.print_list()

    # deleting by value
    print("deleting at end...")
    example.delete_at_end()
    example.print_list()

    # searching in linked list
    print("searching node...")
    if example.search_node(7):
        print("node is found")
    else:
        print("node not found")


if __name__ == '__main__':
    main()

Output

inserting at head...
inserting at end...
inserting after...
[H] 8 -> 7 -> 14 -> 6 -> 12 -> 5 -> 10 -> 20 -> 9 -> None
deleting at head...
[H] 7 -> 14 -> 6 -> 12 -> 5 -> 10 -> 20 -> 9 -> None
deleting by value...
[H] 7 -> 14 -> 6 -> 5 -> 10 -> 20 -> 9 -> None
deleting at end...
[H] 7 -> 14 -> 6 -> 5 -> 10 -> 20 -> None
searching node...
node is found

Doubly Linked List

In a Singly Linked List, we saw that in order to perform basic operations like insert_after(), insert_at_end(), search_by_value(), delete_by_value(), delete_at_end(), we have to traverse the whole list, starting from head node. Also we need to keep track of the previous nodes while inserting or deleting nodes.

This is where Doubly Linked List comes to the rescue. A DLL is bidirectional, meaning each node stores the data (of course), a reference to the next node and ALSO, a reference to the previous node, making it easier to insert and delete nodes from the list.

Node Implementation for a DLL

class Node:
    def __init__(self):
        self.value = None
        self.next = None
        self.prev = None

DLL Implementation

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

    def is_empty(self):
        if self.head is None:
            return True

Insertion in a DLL

There are 3 types of insertion in a DLL:

Insert at Head
Insert at End
Insert After

Deletion in a DLL

There are 3 types of deletion in a DLL:

Delete at Head
Delete at End
Delete by Value

Full DLL Implementation

class Node:
    def __init__(self):
        self.value = None
        self.next = None
        self.prev = None


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

    def is_empty(self):
        if self.head is None:
            return True

    def insert_at_head(self, data):
        if self.is_empty():
            self.head = Node()
            self.head.value = data
            return

        new = Node()
        new.value = data
        new.prev = None
        new.next = self.head

        self.head.prev = new
        self.head = new

    def insert_at_end(self, data):
        if self.is_empty():
            self.insert_at_head(data)
            return

        current = self.head
        while current.next is not None:
            current = current.next

        new = Node()
        new.value = data
        new.next = None

        current.next = new
        new.prev = current

    def insert_after(self, after, data):
        if self.is_empty():
            return

        current = self.head
        while current.next is not None and current.value is not after:
            current = current.next

        if current is None:
            print("can't insert, value not found")
            return

        new = Node()
        new.value = data
        new.prev = current
        new.next = current.next
        if current.next is not None:
            current.next.prev = new
        current.next = new

    def search_node(self, data):
        if self.is_empty():
            return False

        current = self.head
        while current.next is not None:
            if current.value is data:
                return True
            current = current.next

        return False

    def delete_at_head(self):
        if self.is_empty():
            return

        current = self.head
        self.head = current.next
        self.head.prev = None

    def delete_at_end(self):
        if self.is_empty():
            return

        if self.head.next is None:
            self.head = None
            return

        current = self.head
        while current.next is not None:
            current = current.next

        current.prev.next = None

    def delete_by_value(self, data):
        if self.is_empty():
            return

        current = self.head

        if current.value is data:
            self.delete_at_head()
            return

        while current.next is not None:
            if current.value is data:
                current.next.prev = current.prev
                current.prev.next = current.next
                return
            current = current.next

        print("can't delete, value not found")

    def print_list(self):
        if self.is_empty():
            print("list is empty")
            return

        pretty_list = self.prettify()
        print(pretty_list)

    def prettify(self):
        start_tag = "[H] None"
        end_tag = "None"
        printer = ""

        printer += start_tag
        printer += ' <- '

        current = self.head
        while current is not None:
            printer += str(current.value)
            current = current.next

            if current:
                printer += " <-> "
            else:
                printer += " -> "

        printer += end_tag

        return printer

Validating the DLL Implementation

import educative.course1.linkedlists.doubly_linked_list as dll


def main():
    example = dll.DoublyLinkedList()

    # inserting at head
    print("inserting at head...")
    example.insert_at_head(5)
    example.insert_at_head(6)
    example.insert_at_head(7)
    example.insert_at_head(8)

    # inserting at end
    print("inserting at end...")
    example.insert_at_end(10)
    example.insert_at_end(9)

    # inserting after a node
    print("inserting after...")
    example.insert_after(6, 12)
    example.insert_after(7, 14)
    example.insert_after(10, 20)

    # printing list
    example.print_list()

    # deleting at head
    print("deleting at head...")
    example.delete_at_head()
    example.print_list()

    # deleting by value
    print("deleting by value...")
    example.delete_by_value(12)
    example.print_list()

    # deleting by value
    print("deleting at end...")
    example.delete_at_end()
    example.print_list()

    # searching in linked list
    print("searching node...")
    if example.search_node(7):
        print("node is found")
    else:
        print("node not found")


if __name__ == '__main__':
    main()

Output

inserting at head...
inserting at end...
inserting after...
[H] None <- 8 <-> 7 <-> 14 <-> 6 <-> 12 <-> 5 <-> 10 <-> 20 <-> 9 -> None
deleting at head...
[H] None <- 7 <-> 14 <-> 6 <-> 12 <-> 5 <-> 10 <-> 20 <-> 9 -> None
deleting by value...
[H] None <- 7 <-> 14 <-> 6 <-> 5 <-> 10 <-> 20 <-> 9 -> None
deleting at end...
[H] None <- 7 <-> 14 <-> 6 <-> 5 <-> 10 <-> 20 -> None
searching node...
node is found

Linked List with Tail

In this version of Linked Lists, the last element is referred to as tail, in addition to the first element referred to as head. Both SLL and DLL can be implemeted with a tail pointer.

Having a tail pointer, makes it signicantly easy to add or delete elements from end of the linked list.

In terms of time complexity:

Insertion at end in an SLL with tail will only take constant time - O(1) as compared to linear time - O(n) in a simple SLL.
Similarly, insertion at end in a DLL with tail will also only take constant time - O(1) as compared to linear time - O(n) in a simple DLL.
When it comes to deletion at end, and SLL with tail will still take linear time - O(n) because we need to traverse the whole list to keep track of the previous element of the last node.
However for a DLL with tail, we don’t need to traverse the whole list, as the last node (tail) already has a pointer to the previous node of the last node, so it takes constant time - O(1)

Meaning, we see real advantage of using a tail pointer in the case of delete_at_end() for DLLs.

Implementing DLL with Tail

class Node:
    def __init__(self):
        self.value = None
        self.next = None
        self.prev = None


class DoublyLinkedListTail:
    def __init__(self, head=None, tail=None):
        self.head = head
        self.tail = tail

    def is_empty(self):
        if self.head is None and self.tail is None:
            return True

    def insert_at_head(self, data):
        new = Node()
        new.value = data
        new.prev = None

        if self.is_empty():
            new.next = None
            self.head = new
            self.tail = new
        else:
            new.next = self.head
            self.head.prev = new
            self.head = new

    def insert_at_end(self, data):
        if self.is_empty():
            self.insert_at_head(data)
            return

        new = Node()
        new.value = data
        new.next = None
        new.prev = self.tail

        self.tail.next = new
        self.tail = new

    def insert_after(self, prev_data, data):
        if self.is_empty():
            return

        current = self.head
        while current.next is not None and current.value is not prev_data:
            current = current.next

        if current.value is not prev_data:
            print("can't insert, value not found")
            return

        new = Node()
        new.value = data
        new.prev = current

        if current.next is None:
            new.next = None
            self.tail = new
        else:
            new.next = current.next
            current.next.prev = new

        current.next = new

    def search_node(self, data):
        if self.is_empty():
            return False

        current = self.head
        while current.next is not None and current.value is not data:
            current = current.next

        if current.value is data:
            return True
        else:
            return False

    def delete_at_head(self):
        if self.is_empty():
            return

        if self.head.next is None:
            self.head = None
            self.tail = None
        else:
            self.head.next.prev = None
            self.head = self.head.next

    def delete_at_end(self):
        if self.is_empty():
            return

        if self.tail.prev is None:
            self.delete_at_head()
        else:
            self.tail.prev.next = None
            self.tail = self.tail.prev

    def delete_by_value(self, data):
        if self.is_empty():
            return

        if self.head.value is data:
            self.delete_at_head()
            return

        if self.tail.value is data:
            self.delete_at_end()
            return

        current = self.head
        while current.next is not None and current.value is not data:
            current = current.next

        if current.value is not data:
            print("can't delete, value not found")
        else:
            current.prev.next = current.next
            current.next.prev = current.prev

    def print_list(self):
        if self.is_empty():
            print("list is empty")
            return

        pretty_list = self.prettify()
        print(pretty_list)

    def prettify(self):
        start_tag = "[H] None"
        end_tag = "None [T]"
        printer = ""

        printer += start_tag
        printer += ' <- '

        current = self.head
        while current is not None:
            printer += str(current.value)
            current = current.next

            if current:
                printer += " <-> "

        printer += " -> "
        printer += end_tag

        return printer

Validating DLL with Tail

import educative.course1.linkedlists.doubly_linked_list_tail as dll_tail


def main():
    example = dll_tail.DoublyLinkedListTail()

    # inserting at head
    print("inserting at head...")
    example.insert_at_head(5)
    example.insert_at_head(6)
    example.insert_at_head(7)
    example.insert_at_head(8)

    # inserting at end
    print("inserting at end...")
    example.insert_at_end(10)
    example.insert_at_end(9)

    # inserting after a node
    print("inserting after...")
    example.insert_after(6, 12)
    example.insert_after(9, 20)
    example.insert_after(7, 14)
    example.insert_after(20, 15)
    example.insert_after(21, 18)

    # printing list
    example.print_list()

    # deleting at head
    print("deleting at head...")
    example.delete_at_head()
    example.print_list()

    # deleting by value
    print("deleting by value...")
    example.delete_by_value(12)
    example.print_list()

    # deleting by value
    print("deleting at end...")
    example.delete_at_end()
    example.print_list()

    # searching in linked list
    print("searching node...")
    if example.search_node(21):
        print("node is found")
    else:
        print("node not found")


if __name__ == '__main__':
    main()

Output

inserting at head...
inserting at end...
inserting after...
can’t insert, value not found
[H] None <- 8 <-> 7 <-> 14 <-> 6 <-> 12 <-> 5 <-> 10 <-> 9 <-> 20 <-> 15 -> None [T]
deleting at head...
[H] None <- 7 <-> 14 <-> 6 <-> 12 <-> 5 <-> 10 <-> 9 <-> 20 <-> 15 -> None [T]
deleting by value...
[H] None <- 7 <-> 14 <-> 6 <-> 5 <-> 10 <-> 9 <-> 20 <-> 15 -> None [T]
deleting at end...
[H] None <- 7 <-> 14 <-> 6 <-> 5 <-> 10 <-> 9 <-> 20 -> None [T]
searching node...
node not found

Challenges

Challenges 4-10

In the challenges below, we use a singly linked list to solve the problem.

Challenge 4 : Find the Length of a Linked List

Set variable current to the head node of the linked list.
Iterate the linked list until the current element is not None.
Increment a counter with each pass, final value of counter will be the length of the linked list.

import educative.course1.linkedlists.singly_linked_list as sll

elements = [0, 1, 2, 3, 4]
result = 5


def find_length(linked_list):
    count = 0

    current = linked_list.head
    while current:
        count += 1
        current = current.next

    return count


def main():
    linked_list = sll.SinglyLinkedList()
    [linked_list.insert_at_end(x) for x in elements]
    pretty_list = linked_list.prettify()

    print("Input: " + str(pretty_list))
    print("Expected: " + str(result))
    print("Output: " + str(find_length(linked_list)))


if __name__ == '__main__':
    main()

Output

Input: [H] 0 -> 1 -> 2 -> 3 -> 4 -> None
Expected: 5
Output: 5

Challenge 5 : Reverse a Linked List

In-place link swaps

Assume 3 variables prev_node, current and next_node to keep track of nodes while swapping the links.
Set prev_node and next_node to None, current to linked list head.
Now iterate the linked-list while current is not None.
set next_node to current.next.
set current.next to prev_node.
set prev_node to current.
set current to next_node.
After all nodes are iterated, all links are reversed.
Now, current is None and prev_node contains first element of the linked list after reversal.
Finally, set the head variable to prev_node and list is reversed.

import educative.course1.linkedlists.singly_linked_list as sll

incoming_elements = [10, 9, 4, 4, 6]
expected_elements = [6, 4, 4, 9, 10]


def reverse_linked_list(linked_list):
    prev_node = None
    current = linked_list.head
    next_node = None

    while current:
        next_node = current.next
        current.next = prev_node
        prev_node = current
        current = next_node

    linked_list.head = prev_node

    return linked_list.prettify()


def main():
    input_linked_list = sll.SinglyLinkedList()
    [input_linked_list.insert_at_end(x) for x in incoming_elements]

    expected_linked_list = sll.SinglyLinkedList()
    [expected_linked_list.insert_at_end(x) for x in expected_elements]

    print("Input: " + str(input_linked_list.prettify()))
    print("Expected: " + str(expected_linked_list.prettify()))
    print("Output: " + str(reverse_linked_list(input_linked_list)))


if __name__ == '__main__':
    main()

Output

Input: [H] 10 -> 9 -> 4 -> 4 -> 6 -> None
Expected: [H] 6 -> 4 -> 4 -> 9 -> 10 -> None
Output: [H] 6 -> 4 -> 4 -> 9 -> 10 -> None

Challenge 6 : Detect Loop in a Linked List

The most optimum solution to detect loop in a linked list is outlined in Floyd’s Cycle Detection Algorithm.

Using Floyd’s Cycle Detection Algorithm:

Set 2 pointers, slow and fast and set them to head of the linked list.
Slow pointer jumps 1 step from current element to next element.
Fast pointer jumps 2 steps from current element to bext of next element.
Iterate the linked list, until slow or fast or fast.next is None.
Eventually slow and fast pointers will either point to the same node if there is a loop, else there is NO loop.

import educative.course1.linkedlists.singly_linked_list as sll

incoming_input = [7, 14, 21]
expected_output = True


 # using floyd's cycle detection algorithm
def detect_loop(linked_list):
    slow = linked_list.head
    fast = linked_list.head

    while slow and fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow is fast:
            return True

    return False


def main():
    input_linked_list = sll.SinglyLinkedList()
    [input_linked_list.insert_at_end(x) for x in incoming_input]

    # Adding Loop
    input_linked_list.head.next.next.next = input_linked_list.head

    # can't print input_linked_list after adding a loop, so creating
    # a textual representation of a looped input_linked_list to print as Input
    printer = "[H] "
    for i in range(3):
        for x in incoming_input:
            printer += str(x) + ' -> '

    printer += "..."

    print("Input: " + str(printer))
    print("Expected: " + str(expected_output))
    print("Output: " + str(detect_loop(input_linked_list)))


if __name__ == '__main__':
    main()

Output

Input: [H] 7 -> 14 -> 21 -> 7 -> 14 -> 21 -> 7 -> 14 -> 21 -> ...
Expected: True
Output: True

Challenge 7: Find the Middle Value of a Linked List

This is very similar to Floyd’s Cycle Detection Algorithm above

Set 2 variables, mid and current to the linked list head.
For every single jump of mid variable to the next node, current node jumps twice the next node’s next node.
Iterate the list, until either mid, current or current.next is None.
When current = None means current traversed whole linked list.
Since mid variable was only traversing at half speed as compared to current, mid variable now contains the middle node.

import educative.course1.linkedlists.singly_linked_list as sll

incoming_input = [7, 14, 10, 21]
expected_output = 14


 # current pointer jumps twice and mid only jumps once,
 # so when loop terminates, middle value is found
def find_middle(linked_list):
    mid = linked_list.head
    current = linked_list.head

    while mid and current and current.next:
        current = current.next.next
        if current:
            mid = mid.next

    return mid.value


def main():
    input_linked_list = sll.SinglyLinkedList()
    [input_linked_list.insert_at_end(x) for x in incoming_input]

    print("Input: " + str(input_linked_list.prettify()))
    print("Expected: " + str(expected_output))
    print("Output: " + str(find_middle(input_linked_list)))


if __name__ == '__main__':
    main()

Output

Input: [H] 7 -> 14 -> 10 -> 21 -> None
Expected: 14
Output: 14

Challenge 8 : Remove Duplicates from a Linked List

Solution 1: Nested Loop

We traverse the linked list in a nested fashion.
For each node, we traverse the whole linked list deleting the nodes which match the outer node.
While variable current is not None, set variable compare to current.
While compare.next is not None, check if the outer current node’s value is the same as compare.next’s value.
If yes, then set compare.next to compare.next’s next node (meaning delete compare.next), else set compare to compare.next.
Once inner loop concludes, restart the process by setting current to current’s next node - back to step 3. (the original list is already altered as we removed the duplicate during the inner loop).
Finally, return the linked list with unique elements.

import educative.course1.linkedlists.singly_linked_list as sll

incoming_input = [7, 14, 21, 14, 22]
expected_output = [7, 14, 21, 22]


 # nested loop
def remove_duplicates_1(linked_list):
    current = linked_list.head

    # each outer loop element is compared with inner loop
    # one by one (brute force)
    while current:
        compare = current
        # inner loop only checks forward components
        # and deletes a node if it has the same value
        # as the outer loop pointer
        while compare.next:
            if current.value is compare.next.value:
                compare.next = compare.next.next
            else:
                compare = compare.next
        current = current.next

    return linked_list.prettify()


def main():
    input_linked_list = sll.SinglyLinkedList()
    [input_linked_list.insert_at_end(x) for x in incoming_input]

    output_linked_list = sll.SinglyLinkedList()
    [output_linked_list.insert_at_end(x) for x in expected_output]

    print("Input: " + str(input_linked_list.prettify()))
    print("Expected: " + str(output_linked_list.prettify()))
    print("Output: " + str(remove_duplicates_1(input_linked_list)))


if __name__ == '__main__':
    main()

Output

Input: [H] 7 -> 14 -> 21 -> 14 -> 22 -> None
Expected: [H] 7 -> 14 -> 21 -> 22 -> None
Output: [H] 7 -> 14 -> 21 -> 22 -> None

Solution 2: Using Hash Set

Hash sets have the property that it cannot contain any duplicates. Meaning if we can add all linked list elements to a set and recontruct our list from the set, we would eliminate all duplicates.

set prev and current variables to linked list head.
create a new set to store elements.
check if current node’s value already exists in the set.
If yes, then set prev.next to current.next (skipping current element -> duplicate) and current = current.next.
Else add current’s value to set, set prev to current and current = current.next.
Iterate the loop until current is not None.
Finally, the linked list only contains unique elements.

import educative.course1.linkedlists.singly_linked_list as sll

incoming_input = [7, 14, 21, 14, 22]
expected_output = [7, 14, 21, 22]


 # using hash-set
def remove_duplicates_2(linked_list):
    prev = linked_list.head
    current = linked_list.head
    value_set = set()

    while current:
        if current.value not in value_set:
            value_set.add(current.value)
            prev = current
            current = current.next
        else:
            prev.next = current.next
            current = current.next

    return linked_list.prettify()


def main():
    input_linked_list = sll.SinglyLinkedList()
    [input_linked_list.insert_at_end(x) for x in incoming_input]

    output_linked_list = sll.SinglyLinkedList()
    [output_linked_list.insert_at_end(x) for x in expected_output]

    print("Input: " + str(input_linked_list.prettify()))
    print("Expected: " + str(output_linked_list.prettify()))
    print("Output: " + str(remove_duplicates_2(input_linked_list)))


if __name__ == '__main__':
    main()

Output

Input: [H] 7 -> 14 -> 21 -> 14 -> 22 -> None
Expected: [H] 7 -> 14 -> 21 -> 22 -> None
Output: [H] 7 -> 14 -> 21 -> 22 -> None

Challenge 9 : Union & Intersection of Lists

Union of 2 linked list means a linked list with unique elements from both linked lists. Intersection of 2 linked lists means a linked only containing only the common elements from both linked lists.

For Union:

Write a method to delete duplicate elements froma linked list (as above - using sets).
Iterate list 1 and get to the last node in the list.
Now point last node’s next to 2nd linked list’s head, linking both lists into a single list.
Now remove duplicates from this single list using the method written earlier.
Union linked list is ready.

For Intersection:

Write a method to check if a linked list contains an element (check the element against the whole list).
Set current variable to linked list 1’s head.
Iterate linked list 1 and check if the same element also exists in the linked list 2.
If yes, add the element to the output linked list (at the end).
Move to the next iteration and repeat the check in step 3.
Finally output linked list will contain the intersection list.

import educative.course1.linkedlists.singly_linked_list as sll

incoming_input_1 = [15, 22, 8]
incoming_input_2 = [7, 14, 22]
expected_output_union = [15, 22, 8, 7, 14]
expected_output_intersection = [22]


 # the best way to perform union of two linked lists is to connect
 # the tail of list1 and head of list2, and them remove any duplicate
 # items from the merged list.
def union(linked_list_1, linked_list_2):
    current = linked_list_1.head
    while current.next:
        current = current.next

    # linking linked_list_1's tail to linked_list_2's head
    current.next = linked_list_2.head
    # removing duplicates from the combined list
    h_remove_duplicates(linked_list_1)

    return linked_list_1.prettify()


 # The best way to obtain an intersection list of list1 and list2
 # is to check each element of list1 against list2 and copy common nodes
 # to a new intersection list.
def intersection(linked_list_1, linked_list_2):
    output_linked_list = sll.SinglyLinkedList()
    current = linked_list_1.head
    while current:
        # checking if linked_list_2 contains an element with current node's value.
        # if yes, insert in the output linked list
        if h_contains(linked_list_2, current.value):
            output_linked_list.insert_at_end(current.value)
        current = current.next

    return output_linked_list.prettify()


 # Helper function to check value of a node against nodes in a linked list.
 # Returns true if element found, else returns false
def h_contains(linked_list, data):
    current = linked_list.head

    while current:
        if current.value is data:
            return True
        current = current.next

    return False


 # Helper function to remove duplicates from a list.
 # Returns a linked list with only unique elements.
def h_remove_duplicates(linked_list):
    prev = linked_list.head
    current = linked_list.head
    value_set = set()

    while current:
        if current.value not in value_set:
            value_set.add(current.value)
            prev = current
            current = current.next
        else:
            prev.next = current.next
            current = current.next
    return linked_list


def main():
    # import input arrays as input linked lists for union
    input_linked_list_1_union = sll.SinglyLinkedList()
    [input_linked_list_1_union.insert_at_end(x) for x in incoming_input_1]
    input_linked_list_2_union = sll.SinglyLinkedList()
    [input_linked_list_2_union.insert_at_end(x) for x in incoming_input_2]

    # import input arrays as input linked lists for intersection
    input_linked_list_1_intersection = sll.SinglyLinkedList()
    [input_linked_list_1_intersection.insert_at_end(x) for x in incoming_input_1]
    input_linked_list_2_intersection = sll.SinglyLinkedList()
    [input_linked_list_2_intersection.insert_at_end(x) for x in incoming_input_2]

    # import expected output arrays as output linked lists for union
    output_linked_list_union = sll.SinglyLinkedList()
    [output_linked_list_union.insert_at_end(x) for x in expected_output_union]
    output_linked_list_intersection = sll.SinglyLinkedList()
    [output_linked_list_intersection.insert_at_end(x) for x in expected_output_intersection]

    print("Input 1: " + str(input_linked_list_1_union.prettify()))
    print("Input 2: " + str(input_linked_list_2_union.prettify()))

    print("Expected Union: " + str(output_linked_list_union.prettify()))
    print("Output Union: " + str(union(input_linked_list_1_union, input_linked_list_2_union)))

    print("Expected Intersection: " + str(output_linked_list_intersection.prettify()))
    print("Output Intersection: " + str(intersection(input_linked_list_1_intersection, input_linked_list_2_intersection)))


if __name__ == '__main__':
    main()

Output

Input 1: [H] 15 -> 22 -> 8 -> None
Input 2: [H] 7 -> 14 -> 22 -> None
Expected Union: [H] 15 -> 22 -> 8 -> 7 -> 14 -> None
Output Union: [H] 15 -> 22 -> 8 -> 7 -> 14 -> None
Expected Intersection: [H] 22 -> None
Output Intersection: [H] 22 -> None

Challenge 10 : Return the Nth node from End

This solution uses a simple logic. Nth node from the end means (len(linked list) - n + 1)th node from the beginning.

Compute the size of the linked list (as in challenge 4).
Compute m = size - n + 1
Iterate the linked list, until the count = m.
Return node’s value at count = m

import educative.course1.linkedlists.singly_linked_list as sll

incoming_input = [22, 18, 60, 78, 47, 39, 99]
n = 3
expected_output = 47


def return_nth_from_end(linked_list, n):
    # nth from end means size - n + 1 from beginning,
    # so calculate size
    size = 0
    current = linked_list.head
    while current:
        size += 1
        current = current.next

    # m = size - n + 1
    m = size - n + 1

    count = 0
    current = linked_list.head
    while current:
        count += 1
        if count is m:
            return current.value
        current = current.next

    return None


def main():
    input_linked_list = sll.SinglyLinkedList()
    [input_linked_list.insert_at_end(x) for x in incoming_input]

    print("Input: " + str(input_linked_list.prettify()) + ", n = " + str(n))
    print("Expected: " + str(expected_output))
    print("Output: " + str(return_nth_from_end(input_linked_list, n)))


if __name__ == '__main__':
    main()

Output

Input: [H] 22 -> 18 -> 60 -> 78 -> 47 -> 39 -> 99 -> None, n = 3
Expected: 47
Output: 47