Insert an item at the begining of linked list by Python3

Question

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?

The problem is with your display method, you don’t print the heads data.. — sagi
– sagi, Commented Jan 23, 2022 at 15:09
Because your linkedlist constructor initialize the head with the default constructor — sagi
– sagi, Commented Jan 23, 2022 at 15:58

trincot · Accepted Answer · 2022-01-23 17:45:47Z

1

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

answered Jan 23, 2022 at 17:45

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

gggg Over a year ago

Dummy node is the node whose data and next are both None, right? But it is not the first node, just a helper ? @trincot

trincot Over a year ago

The dummy node's data is None, bit its next reference is the "real" head of the list. So it will be None when the length of the list is 0, and will be the first "real" node when the length of the list is not 0. Such a node is also called a "sentinel" node. It is one way you can implement a linked list, but it is not the only one. You can of course also implement a list without that node, and start with head being None. Then your add function would have been correct.

Collectives™ on Stack Overflow

Insert an item at the begining of linked list by Python3

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related