CODEWITHSUNDEEP
python
MJ49
MJ49

Reputation: 123

Single Linked List Python Header and Tail

I'm learning Python coming from C++ and I'm not sure why my insert method in class LinkedList is not working. I'm expecting my Header node to be linked to my Tail Node, but I'm not getting the expected behavior. 

class Node:
    value = None
    nextNode = None

    def __init__(self, value=None):
        self.value = value
        self.nextNode = None

class LinkedList:

    head = Node()
    tail = Node()

    def __init__(self):
        self.head = None
        self.tail = Node()

    #insert a node method
    def insert(self, value):
        #if new list
        if self.head == None:
            newNode = Node(value)
            self.head = newNode
            newNode.nextNode = self.tail
        else:
            newNode = Node(value)
            self.tail.nextNode = newNode
            self.tail = newNode
            newNode.nextNode = self.head



list1 = LinkedList()
list1.insert(23)
list1.insert(50)
print(list1.head.nextNode.value) #Expect this to be 50, but this returns None

Upvotes: 0

Views: 3294

Answers (3)

chadmc
chadmc

Reputation: 81

You don't need to have an elif or the tail.

class Node:
    value = None
    nextNode = None

    def __init__(self, value=None):
        self.value = value
        self.nextNode = None

class LinkedList:

    head = Node()

    def __init__(self):
        self.head = None

    #insert a node method
    def insert(self, value):
        #if new list
        newNode = Node(value)
        if not self.head:
            self.head = newNode
        else:
            #save head's current position
            temp = self.head
            #move head's position until you find a None value for
            #nextNode
            while(temp.nextNode):
                temp = temp.nextNode

            #set the none value to the new node
            temp.nextNode = newNode

    list1 = LinkedList()
    list1.insert(23)
    list1.insert(50)
    list1.insert(50)
    list1.insert(70)
    print(list1.head.value)
    #23
    print(list1.head.nextNode.value)
    #50
    print(list1.head.nextNode.nextNode.value)
    #50
    print(list1.head.nextNode.nextNode.nextNode.value)
    #70

Upvotes: 0

ywbaek
ywbaek

Reputation: 3031

If you are trying to insert a new node as a tail then try this:

class Node:
    def __init__(self, value=None):
        self.value = value
        self.nextNode = None


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

    def insert(self, value):
        new_node = Node(value)
        if not self.head:
            self.head = new_node
        elif self.tail:
            self.tail.nextNode = new_node
            self.tail = new_node
        else:
            self.head.nextNode = new_node
            self.tail = new_node


list1 = LinkedList()
list1.insert(23)
list1.insert(50)
list1.insert(40)
list1.insert(99)

node = list1.head
print('(head)', end=' -> ')
while node:
    print(node.value, end=' -> ')
    node = node.nextNode
print('(tail)')

(head) -> 23 -> 50 -> 40 -> 99 -> (tail)

No need to use class variables.

Upvotes: 2

chepner
chepner

Reputation: 532033

The class is much simpler with a sentinel, but the head should be the sentinel.

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


class LinkedList:
    def __init__(self):
        self.head = Node(0)  # Store the length, or any other metadata you like
        self.tail = self.head  # The tail is just the last item.

    # the list is empty when the head and the tail are the same
    # node (namely, the sentinel)
    def is_empty(self):
        return self.tail is self.head

    def insert(self, value):
        """Add a value to the end of the list"""
        new_node = Node(value)
        self.tail.next = new_node  # Append the node
        self.tail = new_node  # Advance the tail
        self.head.value += 1  # Update the length

And that's all you need. The list maintains two invariants: the head always refers to a sentinel node, and the tail always refers to the last element of the list. Appending to the list just means appending a node after the tail, then updating the tail.

The purpose of the head is to provide an entry point for iterating over the list. The tail is a convenience, to make appending to the end of the list an O(1) operation, rather than having to spend O(n) time iterating from the head to find the last node.

A few exercises:

  1. Write LinkedList.__len__, so you can retrieve the length of a list with len(ll)
  2. Your insert should really be called append. Write a "real" insert method that takes a position to indicate where the new node should be inserted. (ll.insert(0, x) would create a new first element, and ll.insert(n, x) would insert a new element after the n-1 element.)
  3. Write LinkedList.delete to delete an element at the specified position. ll.delete(0) would remove the first element of ll. Note that this should never remove the sentinel, i.e., it's a no-op if ll.is_empty() returns True.

Upvotes: 2

Related Questions