Adding a node to the end of a linkedlist is erasing the existing elements-CodePudding

I am trying to create a linkedlist in Python which consists of various methods. For insertion, I have three methods, add_at_beginning, add_at_position & add_at_end

Node class:

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

Below is my linkedlist.

class LinkedList:
    def __init__(self):
        self.head = None

    def add_at_beginning(self, data):
        temp = Node(data)
        if self.head is None:
            self.head = temp
        else:
            temp.next = self.head
            self.head = temp

    def add_at_end(self, data):
        temp = Node(data)
        if self.head.next is None:
            self.head = temp
        else:
            while self.head.next is not None:
                self.head = self.head.next
            self.head.next = temp

    def add_at_position(self, data, pos):
        temp = Node(data)
        if self.head is None:
            self.head = temp
        else:
            curr = self.head
            i = 1
            while i < pos-1:
                curr = curr.next
                i  = 1
            temp.next = curr.next
            curr.next = temp

    def traverse_linked_list(self):
        if self.head is None:
            print('Empty LinkedList')
        else:
            curr = self.head
            while curr.next is not None:
                print(curr.data)
                curr = curr.next

The problem I am facing is with add_at_end This is my order of insertion.

if __name__ == '__main__':
    ll = LinkedList()
    ll.head = Node(1)
    ll.add_at_beginning(4)
    ll.add_at_beginning(3)
    ll.add_at_beginning(2)
    ll.add_at_position(5, 2)
    ll.traverse_linked_list()

Result: 2, 5, 3, 4

But if I add an element at the end by calling add_at_end, it is erasing every element in the linkedlist. Order of insertion:

ll = LinkedList()
ll.head = Node(1)
ll.add_at_beginning(4)
ll.add_at_beginning(3)
ll.add_at_beginning(2)
ll.add_at_position(5, 2)
ll.add_at_end(10)
ll.traverse_linked_list()

Result: 1

In the method: add_at_end I am traversing until the end of the linkedlist and check if head.next is NONE and only then I am assigning my temp node to self.head.next but the output is completely wrong when I traverse the list after adding elements initially.

Could anyone let me know what is the mistake I did here and how can I fix it ?

CodePudding user response：

I see two corrections:

a) add_at_end:

Do not change self.head. Instead use a dummy like curr you have used in other methods. Changing self.head yields unpredictable result. It should always point to the head of the linked list. So initialize a curr variable to point to your head and then traverse till the end and then assign the temp to the next.

the change would be as below:

def add_at_end(self, data):
     temp = Node(data)
     if self.head is None:
        self.head = temp
        return
     curr = self.head
     while curr.next is not None:
        curr = curr.next
     curr.next = temp

b) When you are traversing linked list to print, you need to check if curr is not None in while loop not curr.next is not None, you check your current node and not the next node before printing.

def traverse_linked_list(self):
      if self.head is None:
          print('Empty LinkedList')
      else:
          curr = self.head
          while curr is not None:
              print(curr.data)
              curr = curr.next

CodePudding user response：

The simplest thing to do might be setting a variable to help you walk to the end, so you don't change the list while you find the end:

position = self.head.next
while position.next is not None:
    position = position.next
position.next = temp

CodePudding user response：

Every time you execute head = head.next, you are dropping one node off the list, starting from the 1st one all the way to the last one and then you append the new (and, now, only) node. This is why you get that result. Other answers already explain how to fix.

Suggestion: If you will be appending at both sides, why not also keep "LinkedList.tail" and "Node.previous" pointers?