List Operations

Syntax of list

The List is the same as arrays irrespective it can store different data types in it. We can access the list by using the start and end range which can be altered by using custom step function as the third argument.

#Syntax : list[ start : end : step ]

Let’s define a variable named myList and declare a list of numbers from 1 to 9 in it.

myList = [1, 2, 3, 4, 5, 6, 7, 8, 9]
#index    0  1  2  3  4  5  6  7  8
#        -9 -8 -7 -6 -5 -4 -3 -2 -1

List Operations

1. List Slicing

List Slicing means accessing the particular element by index or slice or cut a particular range of elements from the List.

Read => Create and write MetaData to a file – Python

print('Original List:',myList)
print('First Element:',myList[0]) #Prints the first element of the list or 0th index of the list
print('Element at 3rd Index position:',myList[2]) #Prints the 3rd element of the list
print('Elements from 0th Index to 4th Index:',myList[0: 5]) #Prints elements of the list from 0th index to 4th index. IT DOESN'T INCLUDE THE LAST INDEX
print('Element at -7th Index:',myList[-7]) #Prints the -7th or 3rd element of the list

2. Append Element to List

#To append an element to a list
myList.append(10)
print('Append:',myList)

3. Index Element

#To find the index of a particular element
print('Index of element \'6\':',myList.index(6)) #returns index of element '6'

4. Sort List

#To sort the list
myList.sort()
print("myList : ",myList)

5. Pop Last Element

#To pop last element
print('Poped Element:',myList.pop())

6. Remove Element

#To remove a particular element from the list BY NAME
myList.remove(6)
print('After removing \'6\':',myList)

7. Insert Element

#To insert an element at a specified Index
myList.insert(5, 6)
print('Inserting \'6\' at 5th index:',myList)

8. Count Element

#To count number of occurences of a element in the list
print('No of Occurences of \'1\':',myList.count(1))

9. Extend List

#To extend a list that is insert multiple elemets at once at the end of the list
myList.extend([11,0])
print('Extending list:',myList)

10. Reverse List

#To reverse a list
myList.reverse()
print('Reversed list:',myList)

Source Code

#Syntax: list[start: end: step]

myList = [1, 2, 3, 4, 5, 6, 7, 8, 9]
#index    0  1  2  3  4  5  6  7  8
#        -9 -8 -7 -6 -5 -4 -3 -2 -1

#List Slicing
print('Original List:',myList)
print('First Element:',myList[0]) #Prints the first element of the list or 0th element of the list
print('Element at 2nd Index position:',myList[2]) #Prints the 2nd element of the list
print('Elements from 0th Index to 4th Index:',myList[0: 5]) #Prints elements of the list from 0th index to 4th index. IT DOESN'T INCLUDE THE LAST INDEX
print('Element at -7th Index:',myList[-7]) #Prints the -7th or 3rd element of the list

#To append an element to a list
myList.append(10)
print('Append:',myList)

#To find the index of a particular element
print('Index of element \'6\':',myList.index(6)) #returns index of element '6'

#To sort the list
myList.sort()

#To pop last element
print('Poped Element:',myList.pop())

#To remove a particular element from the lsit BY NAME
myList.remove(6)
print('After removing \'6\':',myList)

#To insert an element at a specified Index
myList.insert(5, 6)
print('Inserting \'6\' at 5th index:',myList)

#To count number of occurences of a element in the list
print('No of Occurences of \'1\':',myList.count(1))

#To extend a list that is insert multiple elemets at once at the end of the list
myList.extend([11,0])
print('Extending list:',myList)

#To reverse a list
myList.reverse()
print('Reversed list:',myList)

Output

Examples (LL) continued

"""
You are given two non-empty linked lists representing
two non-negative integers. The digits are stored in reverse order
and each of their nodes contain a single digit.
Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero,
except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
"""

import unittest


class Node:
    def __init__(self, x):
        self.val = x
        self.next = None


def add_two_numbers(left: Node, right: Node) -> Node:
    head = Node(0)
    current = head
    sum = 0
    while left or right:
        print("adding: ", left.val, right.val)
        sum //= 10
        if left:
            sum += left.val
            left = left.next
        if right:
            sum += right.val
            right = right.next
        current.next = Node(sum % 10)
        current = current.next
    if sum // 10 == 1:
        current.next = Node(1)
    return head.next


def convert_to_list(number: int) -> Node:
    """
        converts a positive integer into a (reversed) linked list.
        for example: give 112
        result 2 -> 1 -> 1
    """
    if number >= 0:
        head = Node(0)
        current = head
        remainder = number % 10
        quotient = number // 10

        while quotient != 0:
            current.next = Node(remainder)
            current = current.next
            remainder = quotient % 10
            quotient //= 10
        current.next = Node(remainder)
        return head.next
    else:
        print("number must be positive!")


def convert_to_str(l: Node) -> str:
    """
        converts the non-negative number list into a string.
    """
    result = ""
    while l:
        result += str(l.val)
        l = l.next
    return result


class TestSuite(unittest.TestCase):
    """
        testsuite for the linked list structure and
        the adding function, above.
    """

    def test_convert_to_str(self):
        number1 = Node(2)
        number1.next = Node(4)
        number1.next.next = Node(3)
        self.assertEqual("243", convert_to_str(number1))

    def test_add_two_numbers(self):
        # 1. test case
        number1 = Node(2)
        number1.next = Node(4)
        number1.next.next = Node(3)
        number2 = Node(5)
        number2.next = Node(6)
        number2.next.next = Node(4)
        result = convert_to_str(add_two_numbers(number1, number2))
        self.assertEqual("708", result)

        # 2. test case
        number3 = Node(1)
        number3.next = Node(1)
        number3.next.next = Node(9)
        number4 = Node(1)
        number4.next = Node(0)
        number4.next.next = Node(1)
        result = convert_to_str(add_two_numbers(number3, number4))
        self.assertEqual("2101", result)

        # 3. test case
        number5 = Node(1)
        number6 = Node(0)
        result = convert_to_str(add_two_numbers(number5, number6))
        self.assertEqual("1", result)

        # 4. test case
        number7 = Node(9)
        number7.next = Node(1)
        number7.next.next = Node(1)
        number8 = Node(1)
        number8.next = Node(0)
        number8.next.next = Node(1)
        result = convert_to_str(add_two_numbers(number7, number8))
        self.assertEqual("022", result)

    def test_convert_to_list(self):
        result = convert_to_str(convert_to_list(112))
        self.assertEqual("211", result)


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

"""
A linked list is given such that each node contains an additional random
pointer which could point to any node in the list or null.

Return a deep copy of the list.
"""
from collections import defaultdict


class RandomListNode(object):
    def __init__(self, label):
        self.label = label
        self.next = None
        self.random = None


def copy_random_pointer_v1(head):
    """
    :type head: RandomListNode
    :rtype: RandomListNode
    """
    dic = dict()
    m = n = head
    while m:
        dic[m] = RandomListNode(m.label)
        m = m.next
    while n:
        dic[n].next = dic.get(n.next)
        dic[n].random = dic.get(n.random)
        n = n.next
    return dic.get(head)


# O(n)
def copy_random_pointer_v2(head):
    """
    :type head: RandomListNode
    :rtype: RandomListNode
    """
    copy = defaultdict(lambda: RandomListNode(0))
    copy[None] = None
    node = head
    while node:
        copy[node].label = node.label
        copy[node].next = copy[node.next]
        copy[node].random = copy[node.random]
        node = node.next
    return copy[head]

"""
Write a function to delete a node (except the tail)
in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and
you are given the third node with value 3,
the linked list should become 1 -> 2 -> 4 after calling your function.
"""
import unittest


class Node:
    def __init__(self, x):
        self.val = x
        self.next = None


def delete_node(node):
    if node is None or node.next is None:
        raise ValueError
    node.val = node.next.val
    node.next = node.next.next


class TestSuite(unittest.TestCase):
    def test_delete_node(self):

        # make linkedlist 1 -> 2 -> 3 -> 4
        head = Node(1)
        curr = head
        for i in range(2, 6):
            curr.next = Node(i)
            curr = curr.next

        # node3 = 3
        node3 = head.next.next

        # after delete_node => 1 -> 2 -> 4
        delete_node(node3)

        curr = head
        self.assertEqual(1, curr.val)

        curr = curr.next
        self.assertEqual(2, curr.val)

        curr = curr.next
        self.assertEqual(4, curr.val)

        curr = curr.next
        self.assertEqual(5, curr.val)

        tail = curr
        self.assertIsNone(tail.next)

        self.assertRaises(ValueError, delete_node, tail)
        self.assertRaises(ValueError, delete_node, tail.next)


if __name__ == "__main__":

    unittest.main()

"""
    Given a linked list, find the first node of a cycle in it.
    1 -> 2 -> 3 -> 4 -> 5 -> 1  => 1
    A -> B -> C -> D -> E -> C  => C

    Note: The solution is a direct implementation
          Floyd's cycle-finding algorithm (Floyd's Tortoise and Hare).
"""
import unittest


class Node:
    def __init__(self, x):
        self.val = x
        self.next = None


def first_cyclic_node(head):
    """
    :type head: Node
    :rtype: Node
    """
    runner = walker = head
    while runner and runner.next:
        runner = runner.next.next
        walker = walker.next
        if runner is walker:
            break

    if runner is None or runner.next is None:
        return None

    walker = head
    while runner is not walker:
        runner, walker = runner.next, walker.next
    return runner


class TestSuite(unittest.TestCase):
    def test_first_cyclic_node(self):

        # create linked list => A -> B -> C -> D -> E -> C
        head = Node("A")
        head.next = Node("B")
        curr = head.next

        cyclic_node = Node("C")
        curr.next = cyclic_node

        curr = curr.next
        curr.next = Node("D")
        curr = curr.next
        curr.next = Node("E")
        curr = curr.next
        curr.next = cyclic_node

        self.assertEqual("C", first_cyclic_node(head).val)


if __name__ == "__main__":

    unittest.main()

from .reverse import *
from .is_sorted import *
from .remove_range import *
from .swap_in_pairs import *
from .rotate_list import *
from .is_cyclic import *
from .merge_two_list import *
from .is_palindrome import *
from .copy_random_pointer import *

"""
   This function takes two lists and returns the node they have in common, if any.
   In this example:
   1 -> 3 -> 5
               \
                7 -> 9 -> 11
               /
   2 -> 4 -> 6
   ...we would return 7.
   Note that the node itself is the unique identifier, not the value of the node.
   """
import unittest


class Node(object):
    def __init__(self, val=None):
        self.val = val
        self.next = None


def intersection(h1, h2):

    count = 0
    flag = None
    h1_orig = h1
    h2_orig = h2

    while h1 or h2:
        count += 1

        if not flag and (h1.next is None or h2.next is None):
            # We hit the end of one of the lists, set a flag for this
            flag = (count, h1.next, h2.next)

        if h1:
            h1 = h1.next
        if h2:
            h2 = h2.next

    long_len = count  # Mark the length of the longer of the two lists
    short_len = flag[0]

    if flag[1] is None:
        shorter = h1_orig
        longer = h2_orig
    elif flag[2] is None:
        shorter = h2_orig
        longer = h1_orig

    while longer and shorter:

        while long_len > short_len:
            # force the longer of the two lists to "catch up"
            longer = longer.next
            long_len -= 1

        if longer == shorter:
            # The nodes match, return the node
            return longer
        else:
            longer = longer.next
            shorter = shorter.next

    return None


class TestSuite(unittest.TestCase):
    def test_intersection(self):

        # create linked list as:
        # 1 -> 3 -> 5
        #            \
        #             7 -> 9 -> 11
        #            /
        # 2 -> 4 -> 6
        a1 = Node(1)
        b1 = Node(3)
        c1 = Node(5)
        d = Node(7)
        a2 = Node(2)
        b2 = Node(4)
        c2 = Node(6)
        e = Node(9)
        f = Node(11)

        a1.next = b1
        b1.next = c1
        c1.next = d
        a2.next = b2
        b2.next = c2
        c2.next = d
        d.next = e
        e.next = f

        self.assertEqual(7, intersection(a1, a2).val)


if __name__ == "__main__":

    unittest.main()

"""
Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?
"""


class Node:
    def __init__(self, x):
        self.val = x
        self.next = None


def is_cyclic(head):
    """
    :type head: Node
    :rtype: bool
    """
    if not head:
        return False
    runner = head
    walker = head
    while runner.next and runner.next.next:
        runner = runner.next.next
        walker = walker.next
        if runner == walker:
            return True
    return False

def is_palindrome(head):
    if not head:
        return True
    # split the list to two parts
    fast, slow = head.next, head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    second = slow.next
    slow.next = None  # Don't forget here! But forget still works!
    # reverse the second part
    node = None
    while second:
        nxt = second.next
        second.next = node
        node = second
        second = nxt
    # compare two parts
    # second part has the same or one less node
    while node:
        if node.val != head.val:
            return False
        node = node.next
        head = head.next
    return True


def is_palindrome_stack(head):
    if not head or not head.next:
        return True

    # 1. Get the midpoint (slow)
    slow = fast = cur = head
    while fast and fast.next:
        fast, slow = fast.next.next, slow.next

    # 2. Push the second half into the stack
    stack = [slow.val]
    while slow.next:
        slow = slow.next
        stack.append(slow.val)

    # 3. Comparison
    while stack:
        if stack.pop() != cur.val:
            return False
        cur = cur.next

    return True


def is_palindrome_dict(head):
    """
    This function builds up a dictionary where the keys are the values of the list,
    and the values are the positions at which these values occur in the list.
    We then iterate over the dict and if there is more than one key with an odd
    number of occurrences, bail out and return False.
    Otherwise, we want to ensure that the positions of occurrence sum to the
    value of the length of the list - 1, working from the outside of the list inward.
    For example:
    Input: 1 -> 1 -> 2 -> 3 -> 2 -> 1 -> 1
    d = {1: [0,1,5,6], 2: [2,4], 3: [3]}
    '3' is the middle outlier, 2+4=6, 0+6=6 and 5+1=6 so we have a palindrome.
    """
    if not head or not head.next:
        return True
    d = {}
    pos = 0
    while head:
        if head.val in d.keys():
            d[head.val].append(pos)
        else:
            d[head.val] = [pos]
        head = head.next
        pos += 1
    checksum = pos - 1
    middle = 0
    for v in d.values():
        if len(v) % 2 != 0:
            middle += 1
        else:
            step = 0
            for i in range(0, len(v)):
                if v[i] + v[len(v) - 1 - step] != checksum:
                    return False
                step += 1
        if middle > 1:
            return False
    return True

"""
Given a linked list, is_sort function returns true if the list is in sorted
(increasing) order and return false otherwise. An empty list is considered
to be sorted.

For example:
Null :List is sorted
1 2 3 4 :List is sorted
1 2 -1 3 :List is not sorted
"""


def is_sorted(head):
    if not head:
        return True
    current = head
    while current.next:
        if current.val > current.next.val:
            return False
        current = current.next
    return True

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


def kth_to_last_eval(head, k):
    """
    This is a suboptimal, hacky method using eval(), which is not
     safe for user input. We guard against danger by ensuring k in an int
    """
    if not isinstance(k, int) or not head.val:
        return False

    nexts = ".".join(["next" for n in range(1, k + 1)])
    seeker = str(".".join(["head", nexts]))

    while head:
        if eval(seeker) is None:
            return head
        else:
            head = head.next

    return False


def kth_to_last_dict(head, k):
    """
    This is a brute force method where we keep a dict the size of the list
    Then we check it for the value we need. If the key is not in the dict,
    our and statement will short circuit and return False
    """
    if not (head and k > -1):
        return False
    d = dict()
    count = 0
    while head:
        d[count] = head
        head = head.next
        count += 1
    return len(d) - k in d and d[len(d) - k]


def kth_to_last(head, k):
    """
    This is an optimal method using iteration.
    We move p1 k steps ahead into the list.
    Then we move p1 and p2 together until p1 hits the end.
    """
    if not (head or k > -1):
        return False
    p1 = head
    p2 = head
    for i in range(1, k + 1):
        if p1 is None:
            # Went too far, k is not valid
            raise IndexError
        p1 = p1.next
    while p1:
        p1 = p1.next
        p2 = p2.next
    return p2


def print_linked_list(head):
    string = ""
    while head.next:
        string += head.val + " -> "
        head = head.next
    string += head.val
    print(string)


def test():
    # def make_test_li
    # A A B C D C F G
    a1 = Node("A")
    a2 = Node("A")
    b = Node("B")
    c1 = Node("C")
    d = Node("D")
    c2 = Node("C")
    f = Node("F")
    g = Node("G")
    a1.next = a2
    a2.next = b
    b.next = c1
    c1.next = d
    d.next = c2
    c2.next = f
    f.next = g
    print_linked_list(a1)

    # test kth_to_last_eval
    kth = kth_to_last_eval(a1, 4)
    try:
        assert kth.val == "D"
    except AssertionError as e:
        e.args += ("Expecting D, got %s" % kth.val,)
        raise

    # test kth_to_last_dict
    kth = kth_to_last_dict(a1, 4)
    try:
        assert kth.val == "D"
    except AssertionError as e:
        e.args += ("Expecting D, got %s" % kth.val,)
        raise

    # test kth_to_last
    kth = kth_to_last(a1, 4)
    try:
        assert kth.val == "D"
    except AssertionError as e:
        e.args += ("Expecting D, got %s" % kth.val,)
        raise
    print("all passed.")


if __name__ == "__main__":
    test()

# Pros
# Linked Lists have constant-time insertions and deletions in any position,
# in comparison, arrays require O(n) time to do the same thing.
# Linked lists can continue to expand without having to specify
# their size ahead of time (remember our lectures on Array sizing
# from the Array Sequence section of the course!)

# Cons
# To access an element in a linked list, you need to take O(k) time
# to go from the head of the list to the kth element.
# In contrast, arrays have constant time operations to access
# elements in an array.


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


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

"""
Merge two sorted linked lists and return it as a new list. The new list should
be made by splicing together the nodes of the first two lists.

For example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
"""


class Node:
    def __init__(self, x):
        self.val = x
        self.next = None


def merge_two_list(l1, l2):
    ret = cur = Node(0)
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2
    return ret.next


# recursively
def merge_two_list_recur(l1, l2):
    if not l1 or not l2:
        return l1 or l2
    if l1.val < l2.val:
        l1.next = merge_two_list_recur(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_list_recur(l1, l2.next)
        return l2

"""
Write code to partition a linked list around a value x, such that all nodes less
than x come before all nodes greater than or equal to x.  If x is contained
within the list, the values of x only need to be after the elements less than x.
The partition element x can appear anywhere in the "right partition";
it does not need to appear between the left and right partitions.

3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 [partition=5]
3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8

We assume the values of all linked list nodes are int and that x in an int.
"""


class Node:
    def __init__(self, val=None):
        self.val = int(val)
        self.next = None


def print_linked_list(head):
    string = ""
    while head.next:
        string += str(head.val) + " -> "
        head = head.next
    string += str(head.val)
    print(string)


def partition(head, x):
    left = None
    right = None
    prev = None
    current = head
    while current:
        if int(current.val) >= x:
            if not right:
                right = current
        else:
            if not left:
                left = current
            else:
                prev.next = current.next
                left.next = current
                left = current
                left.next = right
        if prev and prev.next is None:
            break
        # cache previous value in case it needs to be pointed elsewhere
        prev = current
        current = current.next


def test():
    a = Node("3")
    b = Node("5")
    c = Node("8")
    d = Node("5")
    e = Node("10")
    f = Node("2")
    g = Node("1")

    a.next = b
    b.next = c
    c.next = d
    d.next = e
    e.next = f
    f.next = g

    print_linked_list(a)
    partition(a, 5)
    print_linked_list(a)


if __name__ == "__main__":
    test()

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


def remove_dups(head):
    """
    Time Complexity: O(N)
    Space Complexity: O(N)
    """
    hashset = set()
    prev = Node()
    while head:
        if head.val in hashset:
            prev.next = head.next
        else:
            hashset.add(head.val)
            prev = head
        head = head.next


def remove_dups_wothout_set(head):
    """
    Time Complexity: O(N^2)
    Space Complexity: O(1)
    """
    current = head
    while current:
        runner = current
        while runner.next:
            if runner.next.val == current.val:
                runner.next = runner.next.next
            else:
                runner = runner.next
        current = current.next


def print_linked_list(head):
    string = ""
    while head.next:
        string += head.val + " -> "
        head = head.next
    string += head.val
    print(string)


# A A B C D C F G

a1 = Node("A")
a2 = Node("A")
b = Node("B")
c1 = Node("C")
d = Node("D")
c2 = Node("C")
f = Node("F")
g = Node("G")

a1.next = a2
a2.next = b
b.next = c1
c1.next = d
d.next = c2
c2.next = f
f.next = g

remove_dups(a1)
print_linked_list(a1)
remove_dups_wothout_set(a1)
print_linked_list(a1)

"""
Given a linked list, remove_range function accepts a starting and ending index
as parameters and removes the elements at those indexes (inclusive) from the list

For example:
List: [8, 13, 17, 4, 9, 12, 98, 41, 7, 23, 0, 92]
remove_range(list, 3, 8);
List becomes: [8, 13, 17, 23, 0, 92]

legal range of the list (0 < start index < end index < size of list).
"""


def remove_range(head, start, end):
    assert start <= end
    # Case: remove node at head
    if start == 0:
        for i in range(0, end + 1):
            if head != None:
                head = head.next
    else:
        current = head
        # Move pointer to start position
        for i in range(0, start - 1):
            current = current.next
        # Remove data until the end
        for i in range(0, end - start + 1):
            if current != None and current.next != None:
                current.next = current.next.next
    return head

"""
Reverse a singly linked list. For example:

1 --> 2 --> 3 --> 4
After reverse:
4 --> 3 --> 2 --> 1
"""
#
# Iterative solution
# T(n)- O(n)
#
def reverse_list(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    if not head or not head.next:
        return head
    prev = None
    while head:
        current = head
        head = head.next
        current.next = prev
        prev = current
    return prev


#
# Recursive solution
# T(n)- O(n)
#
def reverse_list_recursive(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    if head is None or head.next is None:
        return head
    p = head.next
    head.next = None
    revrest = reverse_list_recursive(p)
    p.next = head
    return revrest

"""
Given a list, rotate the list to the right by k places,
where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
"""

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None


def rotate_right(head, k):
    """
    :type head: ListNode
    :type k: int
    :rtype: ListNode
    """
    if not head or not head.next:
        return head
    current = head
    length = 1
    # count length of the list
    while current.next:
        current = current.next
        length += 1
    # make it circular
    current.next = head
    k = k % length
    # rotate until length-k
    for i in range(length - k):
        current = current.next
    head = current.next
    current.next = None
    return head

"""
Given a linked list, swap every two adjacent nodes
and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space.
You may not modify the values in the list,
only nodes itself can be changed.
"""


class Node(object):
    def __init__(self, x):
        self.val = x
        self.next = None


def swap_pairs(head):
    if not head:
        return head
    start = Node(0)
    start.next = head
    current = start
    while current.next and current.next.next:
        first = current.next
        second = current.next.next
        first.next = second.next
        current.next = second
        current.next.next = first
        current = current.next.next
    return start.next

Double Linked List

In single linked list each node of the list has two components, the actual value of the node and the reference to the next node in the linked list. In the doubly linked list, each node has three components: the value of the node, the reference to the previous node, and the reference to the next node. For the start node of the doubly linked list, the reference to the previous node is null. Similarly, for the last node in the doubly linked list, the reference to next node is null.

Pros and Cons of a Doubly Linked List

Following are some of the pros and cons of a doubly linked list:

Pros

Unlike a single linked list, the doubly linked list can be traversed and searched in both directions. The reference to the next node helps in traversing the node in the forward direction while the references to the previous nodes allow traversal in the backward direction.
Basic operations such as insertion and deletion are easier to implement in the doubly linked lists since, unlike single linked lists, we do not need to traverse to the predecessor node and store its reference. Rather, in a doubly linked list the reference of the predecessor node can be retrieved from the node that we want to delete.

Cons

One of the major drawbacks of the doubly linked list is that you need more memory space to store one extra reference for each node.
A few additional steps are required to be performed in order to perform insertion and deletion operations.

Implementing the Doubly Linked List with Python

In this section, we will see how we can create a very simple doubly linked list in Python. If you have read Part 1 and Part 2 of this series of articles, the code should be pretty straight-forward.

As always, let's first create a class for the single node in the list. Add the following code to your file:

class Node:
    def __init__(self, data):
        self.item = data
        self.nref = None
        self.pref = None

You can see in the above code, we create a Node class with three member variables: item, nref, and pref. The item variable will store the actual data for the node. The nref stores the reference to the next node, while pref stores the reference to the previous node in the doubly linked list.

Next, we need to create the DoublyLinkedList class, which contains different doubly linked list related functions. Add the following code:

class DoublyLinkedList:
    def __init__(self):
        self.start_node = None

Throughout this article we will keep adding functions to this class.

Inserting Items in Doubly Linked List

In this section, we will see the different ways of inserting items in a doubly linked list.

Inserting Items in Empty List

The easiest way to insert an item in a doubly linked list is to insert an item in the empty list. The following script inserts an element at the start of the doubly linked list:

 def insert_in_emptylist(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
        else:
            print("list is not empty")

In the script above, we define a method insert_in_emptylist(). The method first checks whether the self.start_node variable is None or not. If the variable is None, it means that the list is actually empty. Next, a new node is created and its value is initialized by the value passed as a parameter to the data parameter of the insert_in_emptylist() function. Finally, the value of self.start_node variable is set to the new node. In case if the list is not empty, a message is simply displayed to the user that the list is not empty.

Add the insert_in_emptylist() method to the DoublyLinkedList class that you created earlier.

Inserting Items at the Start

To insert an item at the beginning of the doubly linked list, we have to first check whether the list is empty or not. If the list is empty, we can simply use the logic defined in the insert_in_emptylist() to insert the element since in an empty list, the first element is always at the start.

Else, if the list is not empty, we need to perform three operations:

For the new node, the reference to the next node will be set to self.start_node.
For the self.start_node the reference to the previous node will be set to the newly inserted node.
Finally, the self.start_node will become the newly inserted node.

The following script inserts an item at the start of the doubly linked list:

    def insert_at_start(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            print("node inserted")
            return
        new_node = Node(data)
        new_node.nref = self.start_node
        self.start_node.pref = new_node
        self.start_node = new_node

Add the insert_at_start() method to the DoublyLinkedList class that you created earlier.

Inserting Items at the End

Inserting an element at the end of the doubly linked list is somewhat similar to inserting an element at the start. At first, we need to check if the list is empty. If the list is empty then we can simply use the insert_in_emptylist() method to insert the element. If the list already contains some element, we traverse through the list until the reference to the next node becomes None. When the next node reference becomes None it means that the current node is the last node.

The previous reference for the new node is set to the last node, and the next reference for the last node is set to the newly inserted node. The script for inserting an item at the last node is as follows:

    def insert_at_end(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            return
        n = self.start_node
        while n.nref is not None:
            n = n.nref
        new_node = Node(data)
        n.nref = new_node
        new_node.pref = n

Add the insert_at_end() method to the DoublyLinkedList class that you created earlier.

Inserting Item after another Item

To insert an item after another item, we first check whether or not the list is empty. If the list is actually empty, we simply display the message that the "list is empty".

Otherwise we iterate through all the nodes in the doubly linked list. In case if the node after which we want to insert the new node is not found, we display the message to the user that the item is not found. Else if the node is found, it is selected and we perform four operations:

Set the previous reference of the newly inserted node to the selected node.
Set the next reference of the newly inserted node to the next reference of the selected.
If the selected node is not the last node, set the previous reference of the next node after the selected node to the newly added node.
Finally, set the next reference of the selected node to the newly inserted node.

The script for inserting item after another item is as follows:

    def insert_after_item(self, x, data):
        if self.start_node is None:
            print("List is empty")
            return
        else:
            n = self.start_node
            while n is not None:
                if n.item == x:
                    break
                n = n.nref
            if n is None:
                print("item not in the list")
            else:
                new_node = Node(data)
                new_node.pref = n
                new_node.nref = n.nref
                if n.nref is not None:
                    n.nref.prev = new_node
                n.nref = new_node

Add the insert_after_item() method to the DoublyLinkedList class that you created earlier.

Inserting Item before another Item

To insert an item before another item, we first check whether or not the list is empty. If the list is actually empty, we simply display the message that the "list is empty".

Otherwise we iterate through all the nodes in the doubly linked list. In case if the node before which we want to insert the new node is not found, we display the message to the user that the item is not found. Else if the node is found, it is selected and we perform four operations:

Set the next reference of the newly inserted node to the selected node.
Set the previous reference of the newly inserted node to the previous reference of the selected.
Set the next reference of the node previous to the selected node, to the newly added node.
Finally, set the previous reference of the selected node to the newly inserted node.

The script for adding item before another item in a doubly linked list is as follows:

    def insert_before_item(self, x, data):
        if self.start_node is None:
            print("List is empty")
            return
        else:
            n = self.start_node
            while n is not None:
                if n.item == x:
                    break
                n = n.nref
            if n is None:
                print("item not in the list")
            else:
                new_node = Node(data)
                new_node.nref = n
                new_node.pref = n.pref
                if n.pref is not None:
                    n.pref.nref = new_node
                n.pref = new_node

Add the insert_before_item() method to the DoublyLinkedList class that you created earlier.

Traversing a Doubly Linked List

Traversing a doubly linked list is very similar to traversing a single linked list. The script is as follows:

    def traverse_list(self):
        if self.start_node is None:
            print("List has no element")
            return
        else:
            n = self.start_node
            while n is not None:
                print(n.item , " ")
                n = n.nref

Add the traverse_list() method to the DoublyLinkedList class that you created earlier.

Deleting Elements from Doubly Linked List

Like insertion, there can be multiple ways to delete elements from a doubly linked list. In this section, we will review some of them.

Deleting Elements from the Start

The easiest way to delete an element from a doubly linked list is from the start. To do so, all you have to do is set the value of the start node to the next node and then set the previous reference of the start node to None. However before we do that we need to perform two checks. First, we need to see if the list is empty. And then we have to see if the list contains only one element or not. If the list contains only one element then we can simply set the start node to None. The following script can be used to delete elements from the start of the doubly linked list.

   def delete_at_start(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            self.start_node = None
            return
        self.start_node = self.start_node.nref
        self.start_prev = None;

Add the delete_at_start() method to the DoublyLinkedList class that you created earlier.

Deleting Elements from the End

To delete the element from the end, we again check if the list is empty or if the list contains a single element. If the list contains a single element, all we have to do is to set the start node to None. If the list has more than one element, we iterate through the list until the last node is reached. Once we reach the last node, we set the next reference of the node previous to the last node, to None which actually removes the last node. The following script can be used to delete the element from the end.

    def delete_at_end(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            self.start_node = None
            return
        n = self.start_node
        while n.nref is not None:
            n = n.nref
        n.pref.nref = None

Add the delete_at_end() method to the DoublyLinkedList class that you created earlier.

Deleting Elements by Value

Deleting an element by value is the trickiest of all the deletion functions in doubly linked lists since several cases have to be handled in order to remove an element by value. Let's first see how the function looks like and then we will see the explanation of the individual piece of code.

    def delete_element_by_value(self, x):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        if self.start_node.nref is None:
            if self.start_node.item == x:
                self.start_node = None
            else:
                print("Item not found")
            return 

        if self.start_node.item == x:
            self.start_node = self.start_node.nref
            self.start_node.pref = None
            return

        n = self.start_node
        while n.nref is not None:
            if n.item == x:
                break;
            n = n.nref
        if n.nref is not None:
            n.pref.nref = n.nref
            n.nref.pref = n.pref
        else:
            if n.item == x:
                n.pref.nref = None
            else:
                print("Element not found")

In the above script we create delete_element_by_value() function that takes the node value as parameter and deletes that node. At the beginining of the function we check if the list is empty or not. If the list is empty we simply display the user that the list is empty.

This logic is implemented in the following piece of code:

        if self.start_node is None:
            print("The list has no element to delete")
            return

Next, we check if the list has a single element and that element is actually the element we want to delete. If the only element is the one that we want to delete, we simply set the self.start_node to None which means that the list will now have no item. If there is only one item and that is not the item that we want to delete, we will simply display the message that item to be deleted is not found.

The following piece of code implements this logic:

        if self.start_node.nref is None:
            if self.start_node.item == x:
                self.start_node = None
            else:
                print("Item not found")
            return

Next, we handle the case where the list has more than one items but the item to be deleted is the first item. In that case we simply execute the logic that we wrote for the method delete_at_start(). The following piece of code deletes an element from the start in case of multiple items:

        if self.start_node.item == x:
            self.start_node = self.start_node.nref
            self.start_node.pref = None
            return

Finally, if the list contains multiple items and the item to be deleted is not the first item, we traverse all the elements in the list except the last one and see if any of the nodes has the value that matches the value be deleted. If the node is found, we perform the following two operations:

Set the value of the next reference of the previous node to the next reference of the node to be deleted.
Set the previous value of the next node to the previous reference of the node to be deleted.

Finally, if the node to be deleted is the last node, the next reference of the node previous to the last node is set to None. The following script implements this logic:

        n = self.start_node
        while n.nref is not None:
            if n.item == x:
                break;
            n = n.nref
        if n.nref is not None:
            n.pref.nref = n.nref
            n.nref.pref = n.pref
        else:
            if n.item == x:
                n.pref.nref = None
            else:
                print("Element not found")

Add the delete_element_by_value() method to the DoublyLinkedList class that you created earlier.

Reversing a Doubly Linked List

To reverse a doubly linked list, you basically have to perform the following operations:

The next reference of the start node should be set none because the first node will become the last node in the reversed list.
The previous reference of the last node should be set to None since the last node will become the previous node.
The next references of the nodes (except the first and last node) in the original list should be swapped with the previous references.

The script for reversing a doubly linked list is as follows:

    def reverse_linked_list(self):
        if self.start_node is None:
            print("The list has no element to delete")
            return 
        p = self.start_node
        q = p.nref
        p.nref = None
        p.pref = q
        while q is not None:
            q.pref = q.nref
            q.nref = p
            p = q
            q = q.pref
        self.start_node = p

Add the reverse_linked_list() method to the DoublyLinkedList class that you created earlier.

Testing Doubly Linked List Functions

In this section, we will test the doubly linked functions that we created in the previous sections.

Let's first create the object of the DoublyLinkedList class. Execute the following script:

new_linked_list = DoublyLinkedList()

Testing Insertion Functions

Let's test the insertion functions first. We'll first add elements in the empty list. Execute the following script:

new_linked_list.insert_in_emptylist(50)

Now if you traverse the list, you should see 50 as the only element in the list as shown below:

new_linked_list.traverse_list()

Output:

Now let's add a few elements at the start. Execute the following script:

new_linked_list.insert_at_start(10)
new_linked_list.insert_at_start(5)
new_linked_list.insert_at_start(18)

Now if you traverse the list, you should see the following elements in the list:

To add the elements at the end, execute the following script:

new_linked_list.insert_at_end(29)
new_linked_list.insert_at_end(39)
new_linked_list.insert_at_end(49)

Now if you traverse the doubly linked list, you should see the following elements:

Let's insert an element after 50.

new_linked_list.insert_after_item(50, 65)

Now the list should look like this:

Finally, let's add an element before item 29.

new_linked_list.insert_before_item(29, 100)

The list at this point of time, should contain the following elements:

Testing Deletion Functions

Let's now test the deletion functions on the items that we inserted in the last sections. Let's first delete an element from the start.

new_linked_list.delete_at_start()

Item 18 will be removed and the list will now look like this:

Similarly, the following script deletes the element from the end of the doubly linked list:

new_linked_list.delete_at_end()

Traversing the list now will return the following items:

Finally, you can also delete the elements by value using the delete_element_by_value() function as shown below:

new_linked_list.delete_element_by_value(65)

If you traverse the list now, you will see that item 65 will be deleted from the list.

Testing Reverse Function

Finally, let's reverse the list using the reverse_linked_list() function. Execute the following script:

new_linked_list.reverse_linked_list()

Now if you traverse the list, you will see the reversed linked list:

Conclusion

The doubly linked list is extremely useful specifically when you have to perform lots of inserts and delete operations. The links to the previous and next nodes make it very easy to insert and delete new elements without keeping track of the previous and next nodes.

In this article, we saw how doubly linked list can be implemented with Python. We also saw different ways to perform insert and delete operations on doubly linked list. Finally we studied how to reverse a doubly linked list.

# 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

    def __repr__(self):
        return (
            "Value: {}, ".format(self.value if self.value else None)
            + "Prev: {}, ".format(self.prev.value if self.prev else None)
            + "Next: {} \n".format(self.next.value if self.next else None)
        )
# 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 pointing 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 pointing 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 __repr__(self):
        return f"Head: {self.head} \n Tail: {self.tail} \n Length: {self.length}"

    def __len__(self):
        return self.length
# Replaces the head of the list with a new value that is passed in.

    def add_to_head(self, value):
        new_node = ListNode(value)
        self.length += 1
# if there is no head or tail, it needs to become both:
        if not self.head and not self.tail:
            self.head = new_node
            self.tail = new_node
# otherwise it only needs to become the head:
        else:
            self.head.prev = new_node
            new_node.next = self.head
            self.head = new_node
# Replaces the tail of the list with a new value that is passed in.

    def remove_from_head(self):
        # if there is no head, just return None because we can't remove
        if not self.head:
            return None
# reduce the length
        self.length -= 1
# we need to store the current head to return it once removed
        current_head = self.head
# if there is solely one node, we set both head and tail to None
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return current_head.value
# changes the head to the next node
        else:
            self.head = self.head.next
  # Removes pointers to any previous node
            self.head.prev = None
            return current_head.value
# Removes the head node and returns the value stored in it.

    def add_to_tail(self, value):
        new_node = ListNode(value)
        self.length += 1
# if there is no head or tail, it needs to become both:
        if not self.head and not self.tail:
            self.head = new_node
            self.tail = new_node
# otherwise it only needs to become the tail:
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
# Removes the tail node and returns the value stored in it

    def remove_from_tail(self):
        # if there is no tail, just return None because we can't remove
        if not self.tail:
            return None
# reduce the length
        self.length -= 1
# we need to store the current tail to return it once removed
        current_tail = self.tail
# if there is solely one node, we set both head and tail to None
        if self.head == self.tail:
            self.head = None
            self.tail = None
            return current_tail.value
# changes the tail to the next node
        else:
            self.tail = self.tail.prev
  # Removes pointers to any next node
            self.tail.next = None
            return current_tail.value
# Takes a reference to a node in the list and moves it to the front of the list, shifting all other list nodes down.

    def move_to_head(self, node):
        # if the passed node is already the head, we just return it
        if node is self.head:
            return node
# if the passed node is the tail, we need to remove it from the tail
        if node is self.tail:
            self.remove_from_tail()
        else:
            node.delete()
            self.length -= 1
# we should add it but only the value of the passed node
        self.add_to_head(node.value)
# Takes a reference to a node in the list and moves it to the end of the list, shifting all other list nodes up.

    def move_to_tail(self, node):
        if node is self.tail:
            return node
        if node is self.head:
            self.remove_from_head()
        else:
            node.delete()
            self.length -= 1
        self.add_to_tail(node.value)
# Takes a reference to a node in the list and removes it from the list. The deleted node's `previous` and `next` pointers should point to each afterwards.

    def delete(self, node):
        if self.head is self.tail:
            self.remove_from_head()
        elif node is self.head:
            self.remove_from_head()
        elif node is self.tail:
            self.remove_from_tail()
        else:
            node.delete()
            return node.value
# Returns the maximum value in the list.

    def get_max(self):
        # if there is no head, we know the list is empty
        if not self.head:
            return None
# we'll set our starting max value as the first value we'll begin looping through in the list, the head
        max_value = self.head.value
# we'll set a current value to check against
        current = self.head
        while current:
            if current.value > max_value:
                max_value = current.value
  # increment current
            current = current.next
# once all values are checked, return max value
        return max_value


ll = DoublyLinkedList()
print(f"ll: {ll}")  # should be empty
ll.add_to_head(2)  # should be 2
ll.add_to_head(5)  # should be 5,2
ll.add_to_head(7)  # should be 7,5,2
ll.remove_from_head()  # should be 5,2
ll.add_to_tail(9)  # should be 5,2,9
ll.add_to_tail(11)  # should be 5,2,9,11
ll.add_to_tail(13)  # should be 5,2,9,11,13
ll.remove_from_tail()  # should be 5,2,9,11
ll.get_max()  # should return 11
print(f"ll: {ll}")  # return length 4, head: 5, tail: 11

List Example

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

class DoubleLinkedList:
    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None

    def prependNode(self, data):
        newNode = Node(data)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
            newNode.next = newNode
            newNode.prev = newNode
        else:
            newNode.next = self.head
            newNode.prev = self.head.prev
            self.head.prev.next = newNode
            self.head.next.prev = newNode

            self.head = newNode

        self.length += 1

    def appendNode(self, data):
        newNode = Node(data)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
            newNode.next = newNode
            newNode.prev = newNode
        else:
            curNode = self.head
            while curNode.next != self.head:
                curNode = curNode.next

            newNode.next = self.head
            newNode.prev = curNode
            curNode.next = newNode
            self.tail = newNode

        self.length += 1

    def printList(self):
        # BUG: Only printing last Node
        if self.length == 0:
            return False
        curNode = self.head
        while curNode.next != self.head:
            print(curNode.data)
            curNode = curNode.next


dLL = DoubleLinkedList()

dLL.prependNode(1)
dLL.prependNode(2)
dLL.prependNode(3)
dLL.prependNode(4)

dLL.printList()

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

class SingleLinkedList:
    def __init__(self):
        self.length = 0
        self.head = None

    def prependNode(self, data):
        newNode = Node(data)
        newNode.next = self.head
        self.head = newNode
        self.length += 1

    def appendNode(self, data):
        newNode = Node(data)

        if self.length == 0:
            self.head = newNode
            self.length += 1
            return
        else:
            curNode = self.head

            while curNode.next != None:
                curNode = curNode.next

            curNode.next = newNode
            self.length += 1

    def deleteNode(self, data):
        if self.length == 0:
            return false
        curNode = self.head
        if curNode.data == data:
            self.head = self.head.next
            curNode = None
            return True
        curNode = self.head
        while curNode.next != None:
            if curNode.next.data == data:
                deleteNode = curNode.next
                curNode.next = curNode.next.next
                deleteNode.next = None
                self.length -= 1
                return True
            else:
                curNode = curNode.next
        return False

    def deleteAllNodes(self, data):
        if(self.length == 0):
            return
        curNode = self.head
        while self.head.data == data:
            self.head = self.head.next
            curNode.next = null
            curNode = self.head
            self.length -= 1
            if curNode == None:
                return

        while curNode.next != None:
            if curNode.next.data == data:
                deleteNode = curNode.next
                curNode.next = curNode.next.next
                deleteNode.next = None
                self.length -= 1
            else:
                curNode = curNode.next

        return deleted


    def isEmpty(self):
        return True if self.length == 0 else False

    def findNode(self, data):
        curNode = self.head

        while curNode.data != data:
            if curNode.next == None:
                return False
            else:
                curNode = curNode.next

        return curNode

    def getNextNode(self, node):
        if(isinstance(node, Node)):
            return node.next;
        return False

    def printList(self):
        curNode = self.head
        while curNode != None:
            print(curNode.data)
            curNode = curNode.next

sLL = SingleLinkedList()
# sLL.appendNode(1)
# sLL.appendNode(2)
# sLL.prependNode(3)
# sLL.appendNode(4)

# sLL.deleteNode(2)
#
# sLL.printList()

# print('List Length: {}'.format(sLL.length))
# print([ m for m in dir(sLL) if not m.startswith('__')])

Linked List

"""
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.prev = prev
        self.value = value
        self.next = next
            
"""
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
    
    """
    Wraps the given value in a ListNode and inserts it 
    as the new head of the list. Don't forget to handle 
    the old head node's previous pointer accordingly.
    """
    def add_to_head(self, value):
        # wrap the input value in a node
        new_node = ListNode(value)
        # increment the length
        self.length += 1
        # 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.next = self.head
            # set the current head's 'prev' to refer to the new_node (added to make it work with DLL)
            self.head.prev = new_node
            # set the list's head reference to the new node 
            self.head = new_node
        
    """
    Removes the List's current head node, making the
    current head's next node the new head of the List.
    Returns the value of the removed Node.
    """
    def remove_from_head(self):
        value = self.head.value
        self.delete(self.head)
        return value
            
    """
    Wraps the given value in a ListNode and inserts it 
    as the new tail of the list. Don't forget to handle 
    the old tail node's next pointer accordingly.
    """
    def add_to_tail(self, value):
        new_node = ListNode(value, None, None)
        self.length += 1
        if not self.tail and not self.head:
            self.tail = new_node
            self.head = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
            
    """
    Removes the List's current tail node, making the 
    current tail's previous node the new tail of the List.
    Returns the value of the removed Node.
    """
    def remove_from_tail(self):
        value = self.tail.value
        self.delete(self.tail)
        return value
            
    """
    Removes the input node from its current spot in the 
    List and inserts it as the new head node of the List.
    """
    def move_to_front(self, node):
        if node is self.head:
            return
        value = node.value
        if node is self.tail:
            self.remove_from_tail()
        else:
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev

            self.length -= 1
        self.add_to_head(value)
        
    """
    Removes the input node from its current spot in the 
    List and inserts it as the new tail node of the List.
    """
    def move_to_end(self, node):
        if node is self.tail:
            return
        value = node.value
        if node is self.head:
            self.remove_from_head()
        else:
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev

            self.length -= 1
        self.add_to_tail(value)

    """
    Deletes the input node from the List, preserving the 
    order of the other elements of the List.
    """
    def delete(self, node):
        if not self.head and not self.tail:
            return
        if self.head is self.tail:
            self.head = None
            self.tail = None
        elif self.head is node:
            self.head = node.next
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev
        elif self.tail is node:
            self.tail = node.prev
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev
        else:
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev
        self.length -= 1

    """
    Finds and returns the maximum value of all the nodes 
    in the List.
    """
    def get_max(self):
        if not self.head:
            return None
        max_val = self.head.value
        current = self.head
        while current:
            if current.value > max_val:
                max_val = current.value
            current = current.next
        return max_val

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_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_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.next)
        self.assertEqual(self.dll.head.value, 9)
        self.assertEqual(self.dll.head.next, self.dll.tail)
        self.assertEqual(self.dll.tail.value, 6)

        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)

        self.dll.delete(self.dll.head)
        self.assertIsNone(self.dll.head)
        self.assertIsNone(self.dll.tail)
        self.assertEqual(len(self.dll), 0)

    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()

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.
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]
[]

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.

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

"""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

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None
 
class SLinkedList:
    def __init__(self):
        self.headval = None
 
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
 
# Link second Node to third node
e2.nextval = e3

from __future__ import annotations

from collections.abc import Iterable, Iterator
from typing import Optional

from graph_examples.linked_lists.base_lists import (
    BaseCircularLinkedList,
    BaseLinearLinkedList,
    BaseDoublyLinkedList,
    BaseSinglyLinkedList,
)
from graph_examples.linked_lists.nodes import LinkedNode, DoublyLinkedNode, CircularLinkedNode, CircularDoublyLinkedNode
from graph_examples.linked_lists.base_nodes import T


class LinkedList(BaseLinearLinkedList[T], BaseSinglyLinkedList[T]):
    def __init__(self, values: Iterable[T] = ()) -> None:
        values_iter = iter(values)
        try:
            self.head = LinkedNode(next(values_iter))
        except StopIteration:
            self.head = None
        node = self.head
        for value in values_iter:
            node.next = LinkedNode(value)
            node = node.next

    def appendleft(self, value: T) -> None:
        self.head = LinkedNode(value, self.head)

    def popleft(self) -> T:
        if not self:
            raise IndexError
        node = self.head
        self.head = node.next
        return node.value

    def reverse(self) -> None:
        node = self.head
        last_node = None
        while node is not None:
            node.next, last_node, node = last_node, node, node.next
        self.head = last_node


class DoublyLinkedList(BaseLinearLinkedList[T], BaseDoublyLinkedList[T]):
    def __init__(self, values: Iterable = ()) -> None:
        values_iter = iter(values)
        try:
            self.head = DoublyLinkedNode(next(values_iter))
        except StopIteration:
            self.head = None
        node = self.head
        for value in values_iter:
            node.next = DoublyLinkedNode(value, None, node)
            node = node.next
        self.tail = node

    def __reversed__(self) -> Iterator[T]:
        node = self.tail
        while node is not None:
            yield node.value
            node = node.last

    def append(self, value: T):
        old_tail = self.tail
        self.tail = DoublyLinkedNode(value, None, old_tail)
        if old_tail is None:
            self.head = self.tail
        else:
            old_tail.next = self.tail

    def appendleft(self, value: T):
        old_head = self.head
        self.head = DoublyLinkedNode(value, old_head)
        if old_head is None:
            self.tail = self.head
        else:
            old_head.last = self.head

    def pop(self) -> T:
        if not self:
            raise IndexError
        old_tail = self.tail
        self.tail = old_tail.last
        if self.tail is None:
            self.head = None
        else:
            self.tail.next = None
        return old_tail.value

    def popleft(self) -> T:
        if not self:
            raise IndexError
        old_head = self.head
        self.head = old_head.next
        if self.head is None:
            self.tail = None
        else:
            self.head.last = None
        return old_head.value

    def reverse(self) -> None:
        node = self.head
        self.head, self.tail = self.tail, self.head
        while node is not None:
            node.next, node.last, node = node.last, node.next, node.next


class CircularLinkedList(BaseCircularLinkedList[T], BaseSinglyLinkedList[T]):
    def __init__(self, values: Iterable[T] = ()):
        values_iter = iter(values)
        try:
            head = CircularLinkedNode(next(values_iter))
        except StopIteration:
            head = None
        node = head
        for value in values_iter:
            node.next = CircularLinkedNode(value, head)
            node = node.next
        self.tail = node

    @property
    def head(self) -> CircularLinkedNode[T]:
        return self.tail.next

    @head.setter
    def head(self, node: CircularLinkedNode[T]):
        self.tail.next = node

    def appendleft(self, value: T) -> None:
        if not self:
            self.tail = CircularLinkedNode(value)
        else:
            self.head = CircularLinkedNode(value, self.head)

    def reverse(self) -> None:
        if not self:
            return
        node = self.head
        last_node = self.tail
        while node is not self.tail:
            node.next, last_node, node = last_node, node, node.next
        self.tail.next, self.tail = last_node, self.head


class CircularDoublyLinkedList(BaseCircularLinkedList[T], BaseDoublyLinkedList[T]):
    tail: Optional[CircularDoublyLinkedNode[T]]
    head: Optional[CircularDoublyLinkedNode[T]]

    def __init__(self, values: Iterable[T] = ()) -> None:
        values_iter = iter(values)
        try:
            head = CircularDoublyLinkedNode(next(values_iter))
        except StopIteration:
            head = None
        node = head
        for value in values_iter:
            node.next = CircularDoublyLinkedNode(value, head, node)
            node = node.next
            head.last = node
        self.tail = node

    @property
    def head(self) -> CircularDoublyLinkedNode[T]:
        return self.tail.next

    def __reversed__(self) -> Iterator[T]:
        if not self:
            return
        yield self.tail.value
        node = self.tail.last
        while node is not self.tail:
            yield node.value
            node = node.last

    def append(self, value: T) -> None:
        if not self:
            self.tail = CircularDoublyLinkedNode(value)
        else:
            self.tail = CircularDoublyLinkedNode(value, self.head, self.tail)
            self.tail.last.next = self.tail
            self.head.last = self.tail

    def appendleft(self, value: T) -> None:
        if not self:
            self.tail = CircularDoublyLinkedNode(value)
        else:
            self.tail.next = CircularDoublyLinkedNode(value, self.head, self.tail)
            self.head.next.last = self.tail.next

    def pop(self) -> T:
        if not self:
            raise IndexError
        value = self.tail.value
        if self.tail is self.head:
            self.tail = None
        else:
            self.tail.last.next, self.head.last, self.tail = self.head, self.tail.last, self.tail.last
        return value

    def popleft(self) -> T:
        if not self:
            raise IndexError
        value = self.head.value
        if self.tail is self.head:
            self.tail = None
        else:
            self.tail.next = self.tail.next.next
            self.tail.next.last = self.tail
        return value

    def reverse(self) -> None:
        if not self:
            return
        node = self.head
        while node is not self.tail:
            node.next, node.last, node = node.last, node.next, node.next
        self.tail.next, self.tail.last, self.tail = self.tail.last, self.tail.next, self.tail.next

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()

Linked List Background

For more background on the different types of data structures in Python, check out the following articles:

Linked List: Introduction

A Linked List is a linear data structure. They are a sequence of data, connected together by links or pointers.

Linked Lists are a chain of nodes, connected together by links. Every node (fundamental block of a linked list) contains the following fields:

Data -> The item to be stored in the node.
Next -> The link or reference to the next node.

In a linked list, the first node is called the head and the last node is determined by the condition that the next points to a null value.

Uses of Linked Lists

Due to their dynamic size allocation and ease of insertion/deletion, linked lists are applied in a lot of use cases.
They’re used to implement a lot of complex data structures like the adjacency list in graphs.
They are used for lifecycle management in operating systems.
A playlist in a music application is implemented using a doubly linked list.
Blockchain, a complex data structure that is used for cryptocurrencies and ledgers use a linked list at their core.

Implementing Linked Lists

There are two main types of Linked Lists:

Singly Linked Lists
Doubly Linked Lists

Singly Linked Lists

In the following example, we’ll implement a singly linked list from scratch in Python. This contains the following methods:

ll.search(head, data) -> Search the given element in the Linked List.
ll.print_list() -> Print the linked list.
ll.size() -> Return the length of the linked list.
ll.insert(ele) -> Insert the given node into the linked list.
ll.delete(data) -> Delete the given element from the linked list.

class Node(object):
	def __init__(self, data):
		self.data = data
		self.next = None

# Class to create a Linked List
class LinkedList(object):
	def __init__(self, head=None):
		self.head = head

	# Search an element and print its index
	def search(self, head, data, index):
		if head.data == data:
			print (index)
		else:
			# Make recursive calls
			if head.next:
				return self.search(head.next, data, index+1)
			else:
				raise ValueError("Node not in linked list")

	# Print the linked list
	def print_list(self):
		if self.head == None:
			raise ValueError("List is empty")

		current = self.head 
		while(current):
			print (current.data, end="  ")
			current = current.next
		print ('\n')

	# Find length of Linked List
	def size(self):
		if self.head == None:
			return 0

		size = 0
		current = self.head
		while(current):
			size += 1
			current = current.next

		return size

	# Insert a node in a linked list
	def insert(self, data):
		node = Node(data)
		if not self.head:
			self.head = node
		else:
			node.next = self.head
			self.head = node

	# Delete a node in a linked list
	def delete(self, data):
		if not self.head:
			return
		
		temp = self.head
		
		# Check if head node is to be deleted
		if head.data == data:
			head = temp.next
			print ("Deleted node is " + str(head.data))
			return

		while(temp.next):
			if (temp.next.data == data):
				print ("Node deleted is " + str(temp.next.data))
				temp.next = temp.next.next
				return
			temp = temp.next
		print ("Node not found")
		return

Doubly Linked Lists

A doubly linked list is similar to a singly linked list. It differs in that it also contains a link to the previous node.

We implement the following methods for the Doubly Linked List data structure:

dll.addNodeLast(x) -> Adds a node at the right end of the linked list.
dll.insertNode(pos, x) -> Adds a node at the position specified.
dll.removeNode(x) -> Removes the specified node.
dll.showReverse() -> Prints the linked list in reverse.
dll.show() -> Prints the linked list.

class Node:
    def __init__(self, val):
        self.value = val
        self.next = None
        self.prev = None
    
class DoublyList:
    def __init__(self, val):
        self.head = Node(val)
        self.tail = self.head

    def addNodeLast(self, val):
        current = self.head
        while current.next != None:
            current = current.next
        newNode = Node(val)
        current.next = newNode
        newNode.prev = current
        self.tail = newNode

    def insertNode(self, val, newVal):
        if self.tail.value == val:
            self.addNodeLast(newVal)
        elif self.head.value == val:
            newNode = Node(newVal)
            newNode.next = self.head.next
            newNode.prev = self.head
            newNode.next.prev = newNode
            self.head.next = newNode
        else:
            current = self.head.next
            while current.value != val:
                current = current.next
            newNode = Node(newVal)
            newNode.next = current.next
            newNode.next.prev = newNode 
            newNode.prev = current
            current.next = newNode

    def removeNode(self, val):
        if self.head.value == val:
            self.head = self.head.next
            self.head.prev = None
        elif self.tail.value == val:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            current = self.head.next
            while current.value != val:
                current = current.next
            current.prev.next = current.next
            current.next.prev = current.prev

    def showReverse(self):
        current = self.tail
        while current != None:
            print(current.value)
            current = current.prev

    def show(self):
        current = self.head
        while current != None:
            print(current.value)
            current = current.next

Practice Linked Lists

First, try implementing the Linked Lists as shown above, and then try running them. Once you’ve mastered the implementation, try the given problem-sets to master linked lists.

Merge Two Sorted Lists -
Remove nth Node from the End of the List -
Rotate List -
Palindrome Linked List -
Construct a Doubly Linked List from 2D Matrix -
Reverse a Doubly Linked List -

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

In a linked list, the first node is called the head and the last node is determined by the condition that the next points to a null value.

We implement the following methods for the Doubly Linked List data structure:

Merge Two Sorted Lists -

Remove nth Node from the End of the List -

Palindrome Linked List -

Construct a Doubly Linked List from 2D Matrix -

Reverse a Doubly Linked List -

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

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

class DoubleLinkedList:
    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None

    def prependNode(self, data):
        newNode = Node(data)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
            newNode.next = newNode
            newNode.prev = newNode
        else:
            newNode.next = self.head
            newNode.prev = self.head.prev
            self.head.prev.next = newNode
            self.head.next.prev = newNode

            self.head = newNode

        self.length += 1

    def appendNode(self, data):
        newNode = Node(data)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
            newNode.next = newNode
            newNode.prev = newNode
        else:
            curNode = self.head
            while curNode.next != self.head:
                curNode = curNode.next

            newNode.next = self.head
            newNode.prev = curNode
            curNode.next = newNode
            self.tail = newNode

        self.length += 1

    def printList(self):
        # BUG: Only printing last Node
        if self.length == 0:
            return False
        curNode = self.head
        while curNode.next != self.head:
            print(curNode.data)
            curNode = curNode.next


dLL = DoubleLinkedList()

dLL.prependNode(1)
dLL.prependNode(2)
dLL.prependNode(3)
dLL.prependNode(4)

dLL.printList()

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

class DoubleLinkedList:
    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None

    def prependNode(self, data):
        newNode = Node(data)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
            newNode.next = newNode
            newNode.prev = newNode
        else:
            newNode.next = self.head
            newNode.prev = self.head.prev
            self.head.prev.next = newNode
            self.head.next.prev = newNode

            self.head = newNode

        self.length += 1

    def appendNode(self, data):
        newNode = Node(data)
        if self.length == 0:
            self.head = newNode
            self.tail = newNode
            newNode.next = newNode
            newNode.prev = newNode
        else:
            curNode = self.head
            while curNode.next != self.head:
                curNode = curNode.next

            newNode.next = self.head
            newNode.prev = curNode
            curNode.next = newNode
            self.tail = newNode

        self.length += 1

    def printList(self):
        # BUG: Only printing last Node
        if self.length == 0:
            return False
        curNode = self.head
        while curNode.next != self.head:
            print(curNode.data)
            curNode = curNode.next


dLL = DoubleLinkedList()

dLL.prependNode(1)
dLL.prependNode(2)
dLL.prependNode(3)
dLL.prependNode(4)

dLL.printList()

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

class SingleLinkedList:
    def __init__(self):
        self.length = 0
        self.head = None

    def prependNode(self, data):
        newNode = Node(data)
        newNode.next = self.head
        self.head = newNode
        self.length += 1

    def appendNode(self, data):
        newNode = Node(data)

        if self.length == 0:
            self.head = newNode
            self.length += 1
            return
        else:
            curNode = self.head

            while curNode.next != None:
                curNode = curNode.next

            curNode.next = newNode
            self.length += 1

    def deleteNode(self, data):
        if self.length == 0:
            return false
        curNode = self.head
        if curNode.data == data:
            self.head = self.head.next
            curNode = None
            return True
        curNode = self.head
        while curNode.next != None:
            if curNode.next.data == data:
                deleteNode = curNode.next
                curNode.next = curNode.next.next
                deleteNode.next = None
                self.length -= 1
                return True
            else:
                curNode = curNode.next
        return False

    def deleteAllNodes(self, data):
        if(self.length == 0):
            return
        curNode = self.head
        while self.head.data == data:
            self.head = self.head.next
            curNode.next = null
            curNode = self.head
            self.length -= 1
            if curNode == None:
                return

        while curNode.next != None:
            if curNode.next.data == data:
                deleteNode = curNode.next
                curNode.next = curNode.next.next
                deleteNode.next = None
                self.length -= 1
            else:
                curNode = curNode.next

        return deleted


    def isEmpty(self):
        return True if self.length == 0 else False

    def findNode(self, data):
        curNode = self.head

        while curNode.data != data:
            if curNode.next == None:
                return False
            else:
                curNode = curNode.next

        return curNode

    def getNextNode(self, node):
        if(isinstance(node, Node)):
            return node.next;
        return False

    def printList(self):
        curNode = self.head
        while curNode != None:
            print(curNode.data)
            curNode = curNode.next

sLL = SingleLinkedList()
# sLL.appendNode(1)
# sLL.appendNode(2)
# sLL.prependNode(3)
# sLL.appendNode(4)

# sLL.deleteNode(2)
#
# sLL.printList()

# print('List Length: {}'.format(sLL.length))
# print([ m for m in dir(sLL) if not m.startswith('__')])

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

`

"""
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.prev = prev
        self.value = value
        self.next = next
            
"""
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
    
    """
    Wraps the given value in a ListNode and inserts it 
    as the new head of the list. Don't forget to handle 
    the old head node's previous pointer accordingly.
    """
    def add_to_head(self, value):
        # wrap the input value in a node
        new_node = ListNode(value)
        # increment the length
        self.length += 1
        # 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.next = self.head
            # set the current head's 'prev' to refer to the new_node (added to make it work with DLL)
            self.head.prev = new_node
            # set the list's head reference to the new node 
            self.head = new_node
        
    """
    Removes the List's current head node, making the
    current head's next node the new head of the List.
    Returns the value of the removed Node.
    """
    def remove_from_head(self):
        value = self.head.value
        self.delete(self.head)
        return value
            
    """
    Wraps the given value in a ListNode and inserts it 
    as the new tail of the list. Don't forget to handle 
    the old tail node's next pointer accordingly.
    """
    def add_to_tail(self, value):
        new_node = ListNode(value, None, None)
        self.length += 1
        if not self.tail and not self.head:
            self.tail = new_node
            self.head = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
            
    """
    Removes the List's current tail node, making the 
    current tail's previous node the new tail of the List.
    Returns the value of the removed Node.
    """
    def remove_from_tail(self):
        value = self.tail.value
        self.delete(self.tail)
        return value
            
    """
    Removes the input node from its current spot in the 
    List and inserts it as the new head node of the List.
    """
    def move_to_front(self, node):
        if node is self.head:
            return
        value = node.value
        if node is self.tail:
            self.remove_from_tail()
        else:
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev

            self.length -= 1
        self.add_to_head(value)
        
    """
    Removes the input node from its current spot in the 
    List and inserts it as the new tail node of the List.
    """
    def move_to_end(self, node):
        if node is self.tail:
            return
        value = node.value
        if node is self.head:
            self.remove_from_head()
        else:
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev

            self.length -= 1
        self.add_to_tail(value)

    """
    Deletes the input node from the List, preserving the 
    order of the other elements of the List.
    """
    def delete(self, node):
        if not self.head and not self.tail:
            return
        if self.head is self.tail:
            self.head = None
            self.tail = None
        elif self.head is node:
            self.head = node.next
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev
        elif self.tail is node:
            self.tail = node.prev
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev
        else:
            if node.prev:
                node.prev.next = node.next
            if node.next:
                node.next.prev = node.prev
        self.length -= 1

    """
    Finds and returns the maximum value of all the nodes 
    in the List.
    """
    def get_max(self):
        if not self.head:
            return None
        max_val = self.head.value
        current = self.head
        while current:
            if current.value > max_val:
                max_val = current.value
            current = current.next
        return max_val

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_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_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.next)
        self.assertEqual(self.dll.head.value, 9)
        self.assertEqual(self.dll.head.next, self.dll.tail)
        self.assertEqual(self.dll.tail.value, 6)

        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)

        self.dll.delete(self.dll.head)
        self.assertIsNone(self.dll.head)
        self.assertIsNone(self.dll.tail)
        self.assertEqual(len(self.dll), 0)

    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()

"""
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()}')

# 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)])

"""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

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None
 
class SLinkedList:
    def __init__(self):
        self.headval = None
 
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
 
# Link second Node to third node
e2.nextval = e3

from __future__ import annotations

from collections.abc import Iterable, Iterator
from typing import Optional

from graph_examples.linked_lists.base_lists import (
    BaseCircularLinkedList,
    BaseLinearLinkedList,
    BaseDoublyLinkedList,
    BaseSinglyLinkedList,
)
from graph_examples.linked_lists.nodes import LinkedNode, DoublyLinkedNode, CircularLinkedNode, CircularDoublyLinkedNode
from graph_examples.linked_lists.base_nodes import T


class LinkedList(BaseLinearLinkedList[T], BaseSinglyLinkedList[T]):
    def __init__(self, values: Iterable[T] = ()) -> None:
        values_iter = iter(values)
        try:
            self.head = LinkedNode(next(values_iter))
        except StopIteration:
            self.head = None
        node = self.head
        for value in values_iter:
            node.next = LinkedNode(value)
            node = node.next

    def appendleft(self, value: T) -> None:
        self.head = LinkedNode(value, self.head)

    def popleft(self) -> T:
        if not self:
            raise IndexError
        node = self.head
        self.head = node.next
        return node.value

    def reverse(self) -> None:
        node = self.head
        last_node = None
        while node is not None:
            node.next, last_node, node = last_node, node, node.next
        self.head = last_node


class DoublyLinkedList(BaseLinearLinkedList[T], BaseDoublyLinkedList[T]):
    def __init__(self, values: Iterable = ()) -> None:
        values_iter = iter(values)
        try:
            self.head = DoublyLinkedNode(next(values_iter))
        except StopIteration:
            self.head = None
        node = self.head
        for value in values_iter:
            node.next = DoublyLinkedNode(value, None, node)
            node = node.next
        self.tail = node

    def __reversed__(self) -> Iterator[T]:
        node = self.tail
        while node is not None:
            yield node.value
            node = node.last

    def append(self, value: T):
        old_tail = self.tail
        self.tail = DoublyLinkedNode(value, None, old_tail)
        if old_tail is None:
            self.head = self.tail
        else:
            old_tail.next = self.tail

    def appendleft(self, value: T):
        old_head = self.head
        self.head = DoublyLinkedNode(value, old_head)
        if old_head is None:
            self.tail = self.head
        else:
            old_head.last = self.head

    def pop(self) -> T:
        if not self:
            raise IndexError
        old_tail = self.tail
        self.tail = old_tail.last
        if self.tail is None:
            self.head = None
        else:
            self.tail.next = None
        return old_tail.value

    def popleft(self) -> T:
        if not self:
            raise IndexError
        old_head = self.head
        self.head = old_head.next
        if self.head is None:
            self.tail = None
        else:
            self.head.last = None
        return old_head.value

    def reverse(self) -> None:
        node = self.head
        self.head, self.tail = self.tail, self.head
        while node is not None:
            node.next, node.last, node = node.last, node.next, node.next


class CircularLinkedList(BaseCircularLinkedList[T], BaseSinglyLinkedList[T]):
    def __init__(self, values: Iterable[T] = ()):
        values_iter = iter(values)
        try:
            head = CircularLinkedNode(next(values_iter))
        except StopIteration:
            head = None
        node = head
        for value in values_iter:
            node.next = CircularLinkedNode(value, head)
            node = node.next
        self.tail = node

    @property
    def head(self) -> CircularLinkedNode[T]:
        return self.tail.next

    @head.setter
    def head(self, node: CircularLinkedNode[T]):
        self.tail.next = node

    def appendleft(self, value: T) -> None:
        if not self:
            self.tail = CircularLinkedNode(value)
        else:
            self.head = CircularLinkedNode(value, self.head)

    def reverse(self) -> None:
        if not self:
            return
        node = self.head
        last_node = self.tail
        while node is not self.tail:
            node.next, last_node, node = last_node, node, node.next
        self.tail.next, self.tail = last_node, self.head


class CircularDoublyLinkedList(BaseCircularLinkedList[T], BaseDoublyLinkedList[T]):
    tail: Optional[CircularDoublyLinkedNode[T]]
    head: Optional[CircularDoublyLinkedNode[T]]

    def __init__(self, values: Iterable[T] = ()) -> None:
        values_iter = iter(values)
        try:
            head = CircularDoublyLinkedNode(next(values_iter))
        except StopIteration:
            head = None
        node = head
        for value in values_iter:
            node.next = CircularDoublyLinkedNode(value, head, node)
            node = node.next
            head.last = node
        self.tail = node

    @property
    def head(self) -> CircularDoublyLinkedNode[T]:
        return self.tail.next

    def __reversed__(self) -> Iterator[T]:
        if not self:
            return
        yield self.tail.value
        node = self.tail.last
        while node is not self.tail:
            yield node.value
            node = node.last

    def append(self, value: T) -> None:
        if not self:
            self.tail = CircularDoublyLinkedNode(value)
        else:
            self.tail = CircularDoublyLinkedNode(value, self.head, self.tail)
            self.tail.last.next = self.tail
            self.head.last = self.tail

    def appendleft(self, value: T) -> None:
        if not self:
            self.tail = CircularDoublyLinkedNode(value)
        else:
            self.tail.next = CircularDoublyLinkedNode(value, self.head, self.tail)
            self.head.next.last = self.tail.next

    def pop(self) -> T:
        if not self:
            raise IndexError
        value = self.tail.value
        if self.tail is self.head:
            self.tail = None
        else:
            self.tail.last.next, self.head.last, self.tail = self.head, self.tail.last, self.tail.last
        return value

    def popleft(self) -> T:
        if not self:
            raise IndexError
        value = self.head.value
        if self.tail is self.head:
            self.tail = None
        else:
            self.tail.next = self.tail.next.next
            self.tail.next.last = self.tail
        return value

    def reverse(self) -> None:
        if not self:
            return
        node = self.head
        while node is not self.tail:
            node.next, node.last, node = node.last, node.next, node.next
        self.tail.next, self.tail.last, self.tail = self.tail.last, self.tail.next, self.tail.next

"""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

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()

class Node(object):
	def __init__(self, data):
		self.data = data
		self.next = None

# Class to create a Linked List
class LinkedList(object):
	def __init__(self, head=None):
		self.head = head

	# Search an element and print its index
	def search(self, head, data, index):
		if head.data == data:
			print (index)
		else:
			# Make recursive calls
			if head.next:
				return self.search(head.next, data, index+1)
			else:
				raise ValueError("Node not in linked list")

	# Print the linked list
	def print_list(self):
		if self.head == None:
			raise ValueError("List is empty")

		current = self.head 
		while(current):
			print (current.data, end="  ")
			current = current.next
		print ('\n')

	# Find length of Linked List
	def size(self):
		if self.head == None:
			return 0

		size = 0
		current = self.head
		while(current):
			size += 1
			current = current.next

		return size

	# Insert a node in a linked list
	def insert(self, data):
		node = Node(data)
		if not self.head:
			self.head = node
		else:
			node.next = self.head
			self.head = node

	# Delete a node in a linked list
	def delete(self, data):
		if not self.head:
			return
		
		temp = self.head
		
		# Check if head node is to be deleted
		if head.data == data:
			head = temp.next
			print ("Deleted node is " + str(head.data))
			return

		while(temp.next):
			if (temp.next.data == data):
				print ("Node deleted is " + str(temp.next.data))
				temp.next = temp.next.next
				return
			temp = temp.next
		print ("Node not found")
		return

class Node:
    def __init__(self, val):
        self.value = val
        self.next = None
        self.prev = None
    
class DoublyList:
    def __init__(self, val):
        self.head = Node(val)
        self.tail = self.head

    def addNodeLast(self, val):
        current = self.head
        while current.next != None:
            current = current.next
        newNode = Node(val)
        current.next = newNode
        newNode.prev = current
        self.tail = newNode

    def insertNode(self, val, newVal):
        if self.tail.value == val:
            self.addNodeLast(newVal)
        elif self.head.value == val:
            newNode = Node(newVal)
            newNode.next = self.head.next
            newNode.prev = self.head
            newNode.next.prev = newNode
            self.head.next = newNode
        else:
            current = self.head.next
            while current.value != val:
                current = current.next
            newNode = Node(newVal)
            newNode.next = current.next
            newNode.next.prev = newNode 
            newNode.prev = current
            current.next = newNode

    def removeNode(self, val):
        if self.head.value == val:
            self.head = self.head.next
            self.head.prev = None
        elif self.tail.value == val:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            current = self.head.next
            while current.value != val:
                current = current.next
            current.prev.next = current.next
            current.next.prev = current.prev

    def showReverse(self):
        current = self.tail
        while current != None:
            print(current.value)
            current = current.prev

    def show(self):
        current = self.head
        while current != None:
            print(current.value)
            current = current.next

Linked List

Linked List

Linked lists in Python

Implementation:

Output:

Common linked list interview questions in Python

Linked List Background

Table of Contents

Linked List: Introduction

Uses of Linked Lists

Implementing Linked Lists

Singly Linked Lists

Doubly Linked Lists

Practice Linked Lists

List Example

List Operations

Syntax of list

List Operations

1. List Slicing

2. Append Element to List

3. Index Element

4. Sort List

5. Pop Last Element

6. Remove Element

7. Insert Element

8. Count Element

9. Extend List

10. Reverse List

List Operations

Syntax of list

List Operations

1. List Slicing

2. Append Element to List

3. Index Element

4. Sort List

5. Pop Last Element

6. Remove Element

7. Insert Element

8. Count Element

9. Extend List

10. Reverse List

Examples (LL) continued

Double Linked List

Pros and Cons of a Doubly Linked List

Implementing the Doubly Linked List with Python

Conclusion

List Example

Linked List

Linked List

Linked lists in Python

Implementation:

Output:

Common linked list interview questions in Python

Linked List Background

Table of Contents

Linked List: Introduction

Uses of Linked Lists

Implementing Linked Lists

Singly Linked Lists

Doubly Linked Lists

Practice Linked Lists