Linked List

ll.py

# linear data structure made up of nodes and refs to the next node

# lets make some node class
class Node:
    def __init__(self, value, next_node = None):
        # value that the node is holding
        self.value = value
        # ref to the next node in the chain
        self.next_node = next_node
    

    def get_value(self):
        """
        Method to get the value of a node
        """
        return self.value

    def get_next(self):
        """
        Method to get the node's "next_node"
        """
        return self.next_node

    def set_next(self, new_next):
        """
        Method to update the node's "next_node" to the new_next
        """
        self.next_node = new_next

    


# now lets think of how we can make nodes interact in a way that consolidates their pieces together

# lets make a LinkedList class
# think of the idea of having a head and a tail like a snake 
# where the snake can grow based upon having more links in it

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

    def add_to_tail(self, value):
        # wrap the value in a new Node
        new_node = Node(value)
        # check if the linked list is empty
        if self.head is None and self.tail is None:
            # set the head and tail to the new node
            self.head = new_node
            self.tail = new_node
        # otherwise the list must have at least one item in there
        else:
            # update the last node's "next_node" to the new node
            self.tail.set_next(new_node) # (last node in chain).next_node = new_node
            # update the "self.tail" to point to the new node that we just added
            self.tail = new_node

    def remove_tail(self):
        """
        remove the last node in the chain and return its value
        """
        # check for empty list
        if self.head is None and self.tail is None:
            # return None
            return None
        # check if there is only one node
        if self.head == self.tail:
            # store the value of the node that we are going to remove
            value = self.tail.get_value()
            # remove the node
            # set head and the tail to None
            self.head = None
            self.tail = None
            # return the stored value
            return value
        # otherwise
        else:
            # store the value of the node that we are going to remove
            value = self.tail.get_value()
            # we need to set the "self.tail" to the second to last node
            # we can only do this by traversing the whole list from beginning to end

            # starting from the head
            current_node = self.head

            # keep iterating until the node after "current_node" is the tail
            while current_node.get_next() != self.tail:
                # keep looping
                current_node = current_node.get_next()

            # at the end of the iteration set "self.tail" to the current_node
            self.tail = current_node
            # set the new tail's "next_node" to None
            self.tail.set_next(None)
            # return Value
            return value
            
    def add_to_head(self, value):
            # wrap the input value in a node
            new_node = Node(value)
            # check if the linked list is empty
            if not self.head and not self.tail:
                # if the list is initially empty, set both head and tail to the new node
                self.head = new_node
                self.tail = new_node
            # we have a non-empty list, add the new node to the head 
            else:
                # set the new node's `next` to refer to the current head
                new_node.set_next(self.head)
                # set the list's head reference to the new node 
                self.head = new_node

    def remove_head(self):
        # check for empty list
        if self.head is None and self.tail is None:
            # return None
            return None
        if self.head == self.tail:
            # store the value of the node that we are going to remove
            value = self.head.get_value()
            # remove the node
            # set head and the tail to None
            self.head = None
            self.tail = None
            # return the stored value
            return value
        else:
            # store the old head's value
            value = self.head.get_value()
            # set self.head to old head's next
            self.head = self.head.get_next()
            # return the value
            return value 



n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)

n1.set_next(n2) # n1.next_node = n2
print(n1.get_value()) # => 2
print('n1',n1)





#OUTPUT:
#1
#n1 <__main__.Node object at 0x0000026367BD0280>

`

Doublely-linked-list.py

DLL-test.py

A Linked List is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object.

Each element of a doubly linked list is an object with an attribute key and two other pointer attributes next and prev.

A list may have one of several forms. It may be either singly linked or doubly linked, it may be sorted or not, and it may be circular or not.

"""
First the Node class needs to be created because every item in a linked list
is a node item containing the data and the pointer to the node it links to
"""


class Node:

    def __init__(self, data):
        self.data = data
        self.nextNode = None


"""
Next the linked list can be created and initialized with the head as none 
because it doesn't exist yet and the number of nodes to 0 because its empty
"""


class LinkedList:

    def __init__(self):
        self.head = None
        self.numOfNodes = 0

        """
        Functions for the LinkedList class:
        """

    # function to insert a new node at the beginning of the list O(1)
    def insert_start(self, data):

        # first increase the number of nodes by 1
        self.numOfNodes = self.numOfNodes + 1
        # then insert the data into the new node
        new_node = Node(data)

        # check to see if there is a head
        if not self.head:
            # if not create it with the new node
            self.head = new_node
        # if there is a head
        else:
            # set the pointer of the new node to the old head
            new_node.nextNode = self.head
            # set the new node as the new head of the list
            self.head = new_node

    # function to insert a new node at the end of the list O(N)
    def insert_end(self, data):

        # first increase the number of nodes by 1
        self.numOfNodes = self.numOfNodes + 1
        # then insert the data into the new node
        new_node = Node(data)

        # get a reference to the head node to begin iteration
        actual_node = self.head

        # iterate the node looking for the node that points to Null
        while actual_node.nextNode is not None:
            # if not the last node pointing to Null
            # change active_node to the next node its pointing to
            actual_node = actual_node.nextNode

        # when we find the node that is pointing to Null
        # change its pointer to point to the new node
        actual_node.nextNode = new_node

    # function to get the size of the linked list O(1)
    def size_of_list(self):
        # return the number of nodes the list contains
        return self.numOfNodes

    # function to traverse the linked list and print all of its nodes data
    def traverse(self):

        # set the reference to the first node
        actual_node = self.head

        # iterate the list while the referenced node is not Null
        while actual_node is not None:
            # print out the actual_node data value
            print(actual_node.data)
            # move the reference to the next node in the list
            actual_node = actual_node.nextNode

    # function to remove a node from the list O(N)
    def remove(self, data):

        # if the list is empty return
        if self.head is None:
            return

        # set the reference to the first node
        actual_node = self.head
        # set the reference to the previous node which is none at first
        previous_node = None

        # iterate the list continuing while the actual_node doesn't contain
        # what we're looking for and isn't Null (empty list or end of list)
        while actual_node is not None and actual_node.data != data:
            # consider  the next node in the list
            # iterate the prev node to current
            previous_node = actual_node
            # iterate the actual node to the next
            actual_node = actual_node.nextNode

        # if we reach the end of the list and don't find a match return
        if actual_node is None:
            return

        # at this point we have found a match
        # first decrease the number of items in the list
        self.numOfNodes -= 1

        # after the while loop ( the node with the data was found)
        # if the previous node is Null then the head node is the one to remove
        if previous_node is None:
            # setting the new head to be the next node will remove the current
            # actual node
            self.head = actual_node.nextNode
        # if previous node is not Null
        else:
            # set the prev.nextNode to be the actual nextNode cutting out the
            # actual node we want to remove
            previous_node.nextNode = actual_node.nextNode



"""
use the functions just created
"""
# create a new LinkedList
linked_list = LinkedList()
# insert a few nodes at the beginning of the list O(1)
linked_list.insert_start(4)
linked_list.insert_start(3)
linked_list.insert_start(7)
# insert a node at the end of the list O(N)
linked_list.insert_end(10)
# remove a node from list O(N)
linked_list.remove(3)
# print the node values of the list O(N)
linked_list.traverse()
# print the size of the list
print(f'size: {linked_list.size_of_list()}')

Linked List

• Given a linked list, in addition to the next pointer, each node has a child pointer that can point to a separate list. With the head node, flatten the list to a single-level linked list.

  • Source

• Reverse a singly linked list. Implement it recursively and iteratively.

• Convert a binary tree to a doubly circular linked list.

• Implement an LRU cache with O(1) runtime for all its operations.

• Check distance between values in linked list.

• A question involving an API's integration with hash map where the buckets of hash map are made up of linked lists.

• Given a singly linked list (a list which can only be traversed in one direction), find the item that is located at 'k' items from the end. So if the list is a, b, c, d and k is 2 then the answer is 'c'. The solution should not search the list twice.

• How can you tell if a Linked List is a Palindrome?

Linked lists in Python

Implementation:

# Singly-Linked List
#
# The linked list is passed around as a variable pointing to the
# root node of the linked list, or None if the list is empty.

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

def linked_list_append(linked_list, value):
    '''Appends a value to the end of the linked list'''
    node = linked_list
    insert_node = LinkedListNode(value)
    if not node:
        return insert_node
    while node.next:
        node = node.next
    node.next = insert_node
    return linked_list

def linked_list_insert_index(linked_list, value, index):
    '''Inserts a value at a particular index'''
    node = linked_list
    insert_node = LinkedListNode(value)
    
    # Check if inserting at head
    if index == 0:
        insert_node.next = node
        return insert_node

    # Skip ahead
    for _ in range(index - 1):
        node = node.next
        if not node:
            raise ValueError
    insert_node.next = node.next
    node.next = insert_node
    return linked_list

def linked_list_delete(linked_list, value):
    '''Deletes the first occurrence of a value in the linked list'''
    node = linked_list
    
    # Check if deleting at head
    if node.value == value:
        return node.next

    # Skip ahead
    while node.next:
        if node.next.value == value:
            node.next = node.next.next
            return linked_list
        node = node.next
    raise ValueError

def linked_list_delete_index(linked_list, index):
    '''Deletes the element at a particular index in the linked list'''
    node = linked_list
    
    # Check if deleting at head
    if index == 0:
        return node.next

    # Skip ahead
    for _ in range(index - 1):
        node = node.next
        if not node:
            raise ValueError
    if not node.next:
        raise ValueError
    node.next = node.next.next
    return linked_list

def linked_list_iter(linked_list):
    '''Lazy iterator over each node in the linked list'''
    node = linked_list
    while node is not None:
        yield node
        node = node.next


# Append to back
linked_list = None    # Start with an empty linked list
linked_list = linked_list_append(linked_list, 1)
linked_list = linked_list_append(linked_list, 2)
linked_list = linked_list_append(linked_list, 4)
print([node.value for node in linked_list_iter(linked_list)])

# Insert by index
linked_list = linked_list_insert_index(linked_list, 0, 0) # Front
print([node.value for node in linked_list_iter(linked_list)])
linked_list = linked_list_insert_index(linked_list, 3, 3) # Back
print([node.value for node in linked_list_iter(linked_list)])

# Delete "3"
linked_list = linked_list_delete(linked_list, 3)
print([node.value for node in linked_list_iter(linked_list)])

# Delete by index
linked_list = linked_list_delete_index(linked_list, 0)
print([node.value for node in linked_list_iter(linked_list)])
linked_list = linked_list_delete_index(linked_list, 1)
print([node.value for node in linked_list_iter(linked_list)])

# Delete until empty
linked_list = linked_list_delete_index(linked_list, 0)
linked_list = linked_list_delete_index(linked_list, 0)
print([node.value for node in linked_list_iter(linked_list)])

Output:

[1, 2, 4]
[0, 1, 2, 4]
[0, 1, 2, 3, 4]
[0, 1, 2, 4]
[1, 2, 4]
[1, 4]
[]

Linked lists are a sequential collection of data that uses relational pointers on each data node to link to the next node in the list.

Unlike arrays, linked lists do not have objective positions in the list. Instead, they have relational positions based on their surrounding nodes.

The first node in a linked list is called the head node, and the final is called the tail node, which has a null pointer.

widget

widget

Linked lists can be singly or doubly linked depending if each node has just a single pointer to the next node or if it also has a second pointer to the previous node.

You can think of linked lists like a chain; individual links only have a connection to their immediate neighbors but all the links together form a larger structure.

Python does not have a built-in implementation of linked lists and therefore requires that you implement a Node class to hold a data value and one or more pointers.

Advantages:

• Efficient insertion and deletion of new elements

• Simpler to reorganize than arrays

• Useful as a starting point for advanced data structures like graphs or trees

Disadvantages:

• Storage of pointers with each data point increases memory usage

• Must always traverse the linked list from Head node to find a specific element

Applications:

• Building block for advanced data structures

• Solutions that call for frequent addition and removal of data

Common linked list interview questions in Python

• Print the middle element of a given linked list

• Remove duplicate elements from a sorted linked list

• Check if a singly linked list is a palindrome

• Merge K sorted linked lists

• Find the intersection point of two linked lists

Implementation

"""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.
Then, use "Test Run" and "Submit" to run the test cases
at the bottom."""

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

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

    def get_position(self, position):
        """Get an element from a particular position.
        Assume the first position is "1".
        Return "None" if position is not in the list."""
        current = self.head
        if(self.head):
            for i in range(position)[1:]:
                if(current.next==None):
                    return None
                else:
                    current=current.next
            return current
        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."""
        current = self.head
        if(self.head):
            for i in range(position)[1:]:
                if(i==position-1):
                    after = current.next
                    current.next = new_element
                    new_element.next = after
                elif(current.next!=None):
                    current = current.next
                else:
                    return 'position out of bounds'
        pass


    def delete(self, value):
        """Delete the first node with a given value."""
        current = self.head
        if(self.head):
            while(current.next!=None):
                if(current.next.value==value):
                    after = current.next.next
                    current.next = after
                else:
                    current = current.next

        if(self.head.value==value):
            after = self.head.next
            self.head = after
        pass

# 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

Simple

Advanced

A linked list is similar to an array, it holds values. However, links in a linked list do not have indexes.

• This is an example of a double ended, doubly linked list.

• Each link references the next link and the previous one.

• A Doubly Linked List (DLL) contains an extra pointer, typically called previous

  pointer, together with next pointer and data which are there in singly linked list.

  • Advantages over SLL - It can be traversed in both forward and backward direction.

    Delete operation is more efficient

"""Each ListNode holds a reference to its previous node
as well as its next node in the List."""
class ListNode:
  def __init__(self, value, prev=None, next=None):
    self.value = value
    self.prev = prev
    self.next = next

  """Wrap the given value in a ListNode and insert it
  after this node. Note that this node could already
  have a next node it is point to."""
  def insert_after(self, value):
    current_next = self.next
    self.next = ListNode(value, self, current_next)
    if current_next:
      current_next.prev = self.next

  """Wrap the given value in a ListNode and insert it
  before this node. Note that this node could already
  have a previous node it is point to."""
  def insert_before(self, value):
    current_prev = self.prev
    self.prev = ListNode(value, current_prev, self)
    if current_prev:
      current_prev.next = self.prev

  """Rearranges this ListNode's previous and next pointers
  accordingly, effectively deleting this ListNode."""
  def delete(self):
    if self.prev:
      self.prev.next = self.next
    if self.next:
      self.next.prev = self.prev

"""Our doubly-linked list class. It holds references to
the list's head and tail nodes."""
class DoublyLinkedList:
  def __init__(self, node=None):
    self.head = node
    self.tail = node
    self.length = 1 if node is not None else 0

  def __len__(self):
    return self.length

  def add_to_head(self, value):
    pass

  def remove_from_head(self):
    pass

  def add_to_tail(self, value):
    pass

  def remove_from_tail(self):
    pass

  def move_to_front(self, node):
    pass

  def move_to_end(self, node):
    pass

  def delete(self, node):
    pass
    
  def get_max(self):
    pass

Test:

import unittest
from doubly_linked_list import ListNode
from doubly_linked_list import DoublyLinkedList

class DoublyLinkedListTests(unittest.TestCase):
  def setUp(self):
    self.node = ListNode(1)
    self.dll = DoublyLinkedList(self.node)

  def test_list_remove_from_tail(self):
    self.dll.remove_from_tail()
    self.assertIsNone(self.dll.head)
    self.assertIsNone(self.dll.tail)
    self.assertEqual(len(self.dll), 0)

    self.dll.add_to_tail(33)
    self.assertEqual(self.dll.head.value, 33)
    self.assertEqual(self.dll.tail.value, 33)
    self.assertEqual(len(self.dll), 1)
    self.assertEqual(self.dll.remove_from_tail(), 33)
    self.assertEqual(len(self.dll), 0)

    self.dll.add_to_tail(68)
    self.assertEqual(len(self.dll), 1)
    self.assertEqual(self.dll.remove_from_tail(), 68)
    self.assertEqual(len(self.dll), 0)

  def test_list_remove_from_head(self):
    self.dll.remove_from_head()
    self.assertIsNone(self.dll.head)
    self.assertIsNone(self.dll.tail)
    self.assertEqual(len(self.dll), 0)

    self.dll.add_to_head(2)
    self.assertEqual(self.dll.head.value, 2)
    self.assertEqual(self.dll.tail.value, 2)
    self.assertEqual(len(self.dll), 1)
    self.assertEqual(self.dll.remove_from_head(), 2)
    self.assertEqual(len(self.dll), 0)
    
    self.dll.add_to_head(55)
    self.assertEqual(len(self.dll), 1)
    self.assertEqual(self.dll.remove_from_head(), 55)
    self.assertEqual(len(self.dll), 0)

  def test_list_add_to_tail(self):
    self.assertEqual(self.dll.tail.value, 1)
    self.assertEqual(len(self.dll), 1)

    self.dll.add_to_tail(30)
    self.assertEqual(self.dll.tail.prev.value, 1)
    self.assertEqual(self.dll.tail.value, 30)
    self.assertEqual(len(self.dll), 2)

    self.dll.add_to_tail(20)
    self.assertEqual(self.dll.tail.prev.value, 30)
    self.assertEqual(self.dll.tail.value, 20)
    self.assertEqual(len(self.dll), 3)

  def test_node_delete(self):
    node_1 = ListNode(3)
    node_2 = ListNode(4)
    node_3 = ListNode(5)

    node_1.next = node_2
    node_2.next = node_3
    node_2.prev = node_1
    node_3.prev = node_2

    node_2.delete()

    self.assertEqual(node_1.next, node_3)
    self.assertEqual(node_3.prev, node_1)

  def test_node_insert_before(self):
    self.node.insert_before(0)
    self.assertEqual(self.node.prev.value, 0)

  def test_list_add_to_head(self):
    self.assertEqual(self.dll.head.value, 1)

    self.dll.add_to_head(10)
    self.assertEqual(self.dll.head.value, 10)
    self.assertEqual(self.dll.head.next.value, 1)
    self.assertEqual(len(self.dll), 2)

  def test_node_insert_after(self):
    self.node.insert_after(2)
    self.assertEqual(self.node.next.value, 2)

  def test_list_move_to_end(self):
    self.dll.add_to_head(40)
    self.assertEqual(self.dll.tail.value, 1)
    self.assertEqual(self.dll.head.value, 40)

    self.dll.move_to_end(self.dll.head)
    self.assertEqual(self.dll.tail.value, 40)
    self.assertEqual(self.dll.tail.prev.value, 1)
    self.assertEqual(len(self.dll), 2)

    self.dll.add_to_tail(4)
    self.dll.move_to_end(self.dll.head.next)
    self.assertEqual(self.dll.tail.value, 40)
    self.assertEqual(self.dll.tail.prev.value, 4)
    self.assertEqual(len(self.dll), 3)

  def test_list_move_to_front(self):
    self.dll.add_to_tail(3)
    self.assertEqual(self.dll.head.value, 1)
    self.assertEqual(self.dll.tail.value, 3)

    self.dll.move_to_front(self.dll.tail)
    self.assertEqual(self.dll.head.value, 3)
    self.assertEqual(self.dll.head.next.value, 1)
    self.assertEqual(len(self.dll), 2)

    self.dll.add_to_head(29)
    self.dll.move_to_front(self.dll.head.next)
    self.assertEqual(self.dll.head.value, 3)
    self.assertEqual(self.dll.head.next.value, 29)
    self.assertEqual(len(self.dll), 3)

  def test_list_delete(self):
    self.dll.delete(self.node)
    self.assertIsNone(self.dll.head)
    self.assertIsNone(self.dll.tail)
    self.assertEqual(len(self.dll), 0)

    self.dll.add_to_tail(1)
    self.dll.add_to_head(9)
    self.dll.add_to_tail(6)

    self.dll.delete(self.dll.head)
    self.assertEqual(self.dll.head.value, 1)
    self.assertEqual(self.dll.tail.value, 6)
    self.assertEqual(len(self.dll), 2)

    self.dll.delete(self.dll.head)
    self.assertEqual(self.dll.head.value, 6)
    self.assertEqual(self.dll.tail.value, 6)
    self.assertEqual(len(self.dll), 1)

  def test_get_max(self):
    self.assertEqual(self.dll.get_max(), 1)
    self.dll.add_to_tail(100)
    self.assertEqual(self.dll.get_max(), 100)
    self.dll.add_to_tail(55)
    self.assertEqual(self.dll.get_max(), 100)
    self.dll.add_to_tail(101)
    self.assertEqual(self.dll.get_max(), 101)

if __name__ == '__main__':
  unittest.main()

ArrayBinary Search TreeLinked ListExtra-ArrayStackBinary TreeRecursionHash TableSearchingSortingQueue SandboxHash TableDouble Linked ListGraphsExoticHeap