Insert an item at the begining of linked list by Python3

How to modify the following code? so that the item can be inserted to the begining of a linked list with add()? why None shows up at the beginning of the linked list? is there anything wrong? I tried several times. It just does not work. What heppened? Any suggestions to change? Is ther any good suggestion when writing a linked list?

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

class linkedlist:
    def __init__(self):
        self.head=Node()
        
def append(self,data):
    cur_node = self.head
    new_node=Node(data)
    while cur_node.next != None:
        cur_node = cur_node.next
    cur_node.next=new_node
    
def display(self):
    lst=[]
    cur_node=self.head
    while cur_node.next!=None:
        cur_node = cur_node.next
        lst.append(cur_node.data)
    return lst
def length(self):
    cur_node=self.head
    c=0
    while cur_node.next!=None:
        cur_node = cur_node.next
        c+=1
    return c
def get(self,index):
    if index >=self.length():
        print('out of bond!')
        return None
    cur_index=0
    cur_node=self.head
    while True:
        cur_node=cur_node.next
        if cur_index==index: return cur_node.data
        cur_index+=1
        
def erase(self,index):
    if index>=self.length():
        print('out of bound')
        return None
    cur_index=0
    cur_node=self.head

          
    while True:
        temp=cur_node
        cur_node=cur_node.next
        if cur_index==index:
            
            temp.next=cur_node.next
            print('erase',index)
            return
        cur_index+=1

def add(self,data):
    cur_node=Node(data)
    cur_node.next=self.head
    self.head=cur_node



LL=linkedlist()

LL.append(1)

LL.append(2)

LL.append(3)
LL.append(4)

print(LL.add(999))
print(LL.display())

None
[None, 1, 2, 3, 4]

Why there is no 999 and How to remove None at the begining?

Answer

Since the Linked List is created with a dummy node as head, and all other methods depend on that assumption, add should never replace it. The idea behind this dummy node, is that it will always be there and never change. It helps to keep code simple (at the cost of the memory for one extra node).

So avoid that add changes the head attribute. The new node should be inserted just after that head:

def add(self,data):
    cur_node=Node(data)
    cur_node.next=self.head.next
    self.head.next=cur_node

Advertisement

Answer