How to implement linked list using OOP?

Question

I'm trying to implement a linked list using OOPs and private variables. However, I'm getting 'str' object has no attribute 'get_data' when I call the display method of the LinkedList class. Also, I feel the add method is also not correct.

When I print self.__head and self.__tail in add(), the code never enters the else part and it outputs:

Sugar Sugar
Milk Milk
Tea Tea
Biscuit Biscuit

Below is my code:

class LinkedList:
    def __init__(self):
        self.__head=None
        self.__tail=None

    def get_head(self):
        return self.__head

    def get_tail(self):
        return self.__tail

    def add(self,data): # Skeptical about it

        if self.__tail is None:
            self.__head=Node(data).get_data()
            self.__tail = self.__head
            print(self.__head,self.__tail)
        else:
            b=Node(data)
            self.__tail= b.get_data()
            self.__head = self.__tail
            b.set_next(self.__tail)
            self.__tail = b.get_next()

            print(self.__head,self.__tail)


    def display(self): # Gives the error

        temp = self.__head
        msg = []
        c = Node(temp)
        while (temp is not None):
            print(temp.get_data())

            msg.append(str(temp.get_data()))

            temp = temp.get_next()

        msg = ''.join(msg)
        print(msg)

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

    def get_data(self):
        return self.__data

    def set_data(self,data):
        self.__data=data

    def get_next(self):
        return self.__next

    def set_next(self,next_node):
        self.__next=next_node


list1=LinkedList()
list1.add("Sugar")

#print(list1.get_head())
#print("Element added successfully")

list1.add("Milk")
list1.add("Tea")
list1.add("Biscuits")
list1.display()

Answer 1

Here's a way to do it more concisely by using several singly-linked-list implementation "tricks" I know about.

A linked-list is always composed of at least one sentinel node which is automatically created and stored in the instance attribute self._tail. Having it has has a couple of benefits.

1. Knowing where the tail is make adding something to the end quick and easy.
2. The list is never empty, so that special case needn't be to checked. A nice side-effect of that means that iterating through elements of the list requires only following the self._next until it's the sentinel node—a single conditional expression.

The other "trick" is when adding a new last element right before the current sentinel node—which sound slow to do in singly-linked-list because it appears to require modifying the Node to the one being added. To achieve the effect of doing this, but avoiding actually doing so, what it does is turn the existing sentinel node into what a new Node would contain, and make's its _next attribute be a new sentinel it creates to replace previous one that's be reused.

How that helps understand what's going on in the following code:

class LinkedList:
    def __init__(self):
        self._tail = Node()
        self._head = self._tail

    def add(self, data):
        """ Add an item to the end of the linked list. """
        new_tail = Node()
        self._tail.set_data(data)  # Convert existing tail into a data node.
        self._tail.set_next(new_tail)
        self._tail = new_tail

        print('adding:', data)

    def display(self):
        """ Traverse linked list and print data associated with each Node. """
        print('\nLinked list contents:')
        curr = self._head
        while curr is not self._tail:
            print('  ' + curr.get_data())
            curr = curr.get_next()


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

    def get_data(self):
        return self._data

    def set_data(self, data):
        self._data = data

    def get_next(self):
        return self._next

    def set_next(self, next_node):
        self._next = next_node


if __name__ == '__main__':
    list1 = LinkedList()

    list1.add("Sugar")
    list1.add("Milk")
    list1.add("Tea")
    list1.add("Biscuits")

    list1.display()

Output:

adding: Sugar
adding: Milk
adding: Tea
adding: Biscuits

Linked list contents:
  Sugar
  Milk
  Tea
  Biscuits

Answer 2

So, I have worked out an answer to my problem. Thank you, everyone, for the help. I'm still not clear about this:

I know python doesn't by default come with private variables when compared to languages like Java, but I believe python is about respecting conventions and '__' is a convention to tell another developer that this particular entity is private.

However, in my case, I wouldn't be able to access the data and next attributes of Node class form LinkedList class and vice versa directly as the name gets resolved to _Classnmae__attribute_name when using private variables. So a better solution is to use getters and setters, because common that is what they are for.

def add(self,data):
    #Remove pass and write the logic to add an element
    new_node = Node(data)
    if self.__head is None:
        self.__head = self.__tail = new_node
    else:
        self.__tail.set_next(new_node)
        self.__tail = new_node

def display(self):
    #Remove pass and write the logic to display the elements
    temp = self.__head       
    msg = []
    c = Node(temp)
    while (temp is not None):
        msg.append(str(temp.get_data()))
        temp = temp.get_next()
    msg = ' '.join(msg)
    print(msg)

Algorithm:

add(data)

1. Create a new node with the data

2. If the linked list is empty (head node is not referring to any other node), make the head node and the tail node refer to the new node

3. Otherwise,

   a. Make the tail node’s link refer to new node

   b. Call the new node as tail node

Answer 3

This seems suspicious:

self.__head = Node(data).get_data()

Considering you're not even referencing the node anymore... Then trying to call the methods of the Node object. Even then your implementation is still wrong.

I'm sure there's other issues but you can google this or actually do your own project / homework.