Python Linked List - insert method

Question

I am kinda new to DataStructure and I trying to write LinkedList, but I cannot figure out why my insert method does not work. If you have any suggestions to improve, please write to me

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


class LinkedList:
    def __init__(self):
        self.start_node = None
        self.index = 0

    def append(self, val):
        new = Node(val)

        if not self.start_node:
            self.start_node = new
            return

        last = self.start_node
        while last.ref:
            last = last.ref
        last.ref = new

        self.index += 1

    def insert(self, index, value):
        start_counting = 0
        start = self.start_node

        while start_counting < index:
            start = start.ref
            start_counting += 1

        NewNode = Node(value)
        tmp = start.ref
        start = NewNode
        start.ref = tmp

    def display(self):
        ls = []
        last = self.start_node
        while last:
            ls.append(last.item)
            last = last.ref
        return ls

start.next = tmp What is the next attribute? Your definition of the Node class has a ref attribute, not a next attribute. — John Gordon
– John Gordon, Commented Jan 5, 2021 at 2:31

Lucas Belfanti · Accepted Answer · 2021-01-05 03:19:15Z

The insert function is replacing the current node instead of linking it. I'll illustrate this with an example:

I have this linked list: 1 -> 2 -> 3 And I want to insert an element "4" in position 1 (the current number in position 1 is 2). The iterations will be:

start_counting = 0
start = self.start_node (node with value 1)

1st Iteration:

start_counting < 1 -> true

start = start.ref (node with value 2)
start_counting += 1 (actual count 1)

2nd Iteration:

start_counting < 1 -> false

start = (node with value 2)

After that the code continues as follows:

We create the new Node (4 in my example) and we do:

tmp = start.ref (which is 3)
start = NewNode (we are replacing the node completely, we are not linking the node with another) <- here is the error
start.ref = tmp (which in this case is 3)

To fix the error you should take in consideration two things:

Iterate until the previous node instead until the next one.
Handle the case where you want to insert a node as head of the linked list, in other words, in position 0.

The code would be something like:

    def insert(self, index, value):
        start_counting = 0
        start = self.start_node
        NewNode = Node(value)

        if index == 0: # Handling the position 0 case.
            NewNode.ref = start
            self.start_node = NewNode
        else:
            while start_counting < index - 1: # Iterating until the previous node.
                start_counting += 1
                start = start.ref

            NewNode.ref = start.ref
            start.ref = NewNode

Tested with the following code and it is working:

a = LinkedList()
a.append(1)
a.append(2)
a.append(3)
a.insert(0, 4)
a.insert(1, 5)
print(a.display())

Yilmaz · Accepted Answer · 2021-01-06 10:06:17Z

Linked list is not indexed, so you do not need to start from index=0. also for linked list, there are 3 insert methods, insert_to_first,insert_to_last or insert_to_any_position. You are implementing insert_to_any position.

def insert(self, index, value):
    start_counting = 0
    start = self.start_node

    while start_counting < index:
        start = start.ref
        start_counting += 1
    # so far no issue
    NewNode = Node(value,None) # new Node accepts 2 args
    # Let's write a linked list to visualize
    # A->B->C-> adding_Node_Here ->D->E... make sure we dont lose ref to D when we inser
    # after while loop, we end up start=C
    NewNode.ref=start.ref # we keep the ref to D
    start.ref=NewNode # now C refs to NewNode
    self.index+=1 # again linked list is not indexed. "size" is better term

Collectives™ on Stack Overflow

Python Linked List - insert method

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related