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

• John Gordon: start.next = tmp What is the next attribute? Your definition of the Node class has a ref attribute, not a next attribute.
• Benku BBB: I edited to start.ref

Answer 1

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:

1. Iterate until the previous node instead until the next one.
2. 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())

Answer 2

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