CODEWITHSUNDEEP
pythonalgorithmdata-structureslinked-listsingly-linked-list
Taimoor Ahmad
Taimoor Ahmad

Reputation: 559

Inserting node at tail efficiently in linked list for Python

I'm trying to implement a singly linked list that inserts and deletes to both sides in O(1) time. To do this I'm saving a pointer to head and tail.

The trouble I'm running into is my insert_tail method. Here's my pseudocode:

If there is no head or tail,
    Set the head AND tail to the new Node
Otherwise,
    Insert the new node as a child of the tail
    Set the tail to that new node

Here's my Python 3 code:

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

    def __str__(self):
        if self.next:
            return "{} -> {}".format(self.val, self.next.val)
        else:
            return "{}".format(self.val)


class LinkedList():
    def __init__(self, init):
        self.head = Node(init)
        self.tail = Node(init)

    # Search at O(n)
    def search(self, val) -> Node:
        pass

    # Insert head or tail at O(1). Returns new node.
    def insert_head(self, val) -> None:
        inserting = Node(val)
        inserting.next = self.head

        self.head = inserting

        # Inserting to empty case
        if self.tail == None:
            self.head = inserting
            self.tail = inserting

        return self.head

    def insert_tail(self, val) -> None:
        inserting = Node(val)

        # Inserting to empty case
        if self.head == None and self.tail == None:
            self.head = inserting
            self.tail = inserting

        else:
            # Change the value of the tail
            self.tail.next = inserting
            self.tail = self.tail.next

    # Insert average case O(n) + 1
    def insert(self, val) -> Node:
        pass

    # Delete at O(1).
    def delete(self, val) -> None:
        pass

    def __str__(self):
        return str(list(self))

    def __iter__(self):
        node = self.head
        while node:
            yield node.val

            node = node.next


# 14, 12, 11, 19, 17, 16, 30, 18, 22, 21, 24, 23, 15
linked = LinkedList(30)

linked.insert_head(16)
linked.insert_head(17)
linked.insert_head(19)
linked.insert_head(11)
linked.insert_head(12)
linked.insert_head(14)
print(linked)

linked.insert_tail(18)
linked.insert_tail(22)
linked.insert_tail(21)
linked.insert_tail(24)
linked.insert_tail(23)
linked.insert_tail(15)
print(linked) # Should actually be: [14, 12, 11, 19, 17, 16, 30, 18, 22, 21, 24, 23, 15]
# But instead it printsas if a new tail was never inserted: [14, 12, 11, 19, 17, 16, 30]

Upvotes: 0

Views: 611

Answers (1)

kaya3
kaya3

Reputation: 51122

To do deletes on both sides in O(1) time, you need a doubly-linked list; otherwise finding the new tail after a delete requires iterating through from the head.

Upvotes: 3

Related Questions