CODEWITHSUNDEEP
python-3.xlinked-list
4daJKong
4daJKong

Reputation: 2045

Basic concept: how to define a linked list in python?

I know the definition of linked list...each unit have data and point to the next...but how did it implement in python? I am really confused about that...

For example, compare with list in python, if I want to create a list:

l1 = [1, 2, 3]

if I want to add element to this list, just use append() or insert() it is very easy

However, many material said it is need to create a class if you want make a linked list like:

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

    def has_value(self, value):
        if self.data == value:
            return True
        else:
            return False
node1 = ListNode(2)
node2 = ListNode(1.2)
node3 = ListNode('a')

I was wondering if there is some way can make it easier like:

(1.2) = (2).next
 ('a') = (1.2).next

Besides, I find some methods likne .val .next .head, when can it be used?

Upvotes: 0

Views: 200

Answers (1)

TheCoder
TheCoder

Reputation: 51

You are confusing Python lists with linked lists. They are not the same. The one you mention first is a Python list. And the one you mention with a Class, is a Linked List.

LISTS :

  • Python lists are just dynamic arrays.
  • Elements of an array are stored at contiguous locations.
  • Lists are dynamic arrays that means their size is not fixed, it is variable, it can be expanded or shrunk as required.
  • Time Complexities : Insertion : O(n), Deletion : O(n), Accessing an element : O(1)

LINKED LISTS :

  • Whereas a linked list is an altogether different data structure where the elements are not stored at contiguous locations, rather linked to each other.
  • Here each element has a link to next element in the list. For the last element of the list, it points to NULL.
  • Time Complexities : Insertion : O(1), Deletion : O(1), Accessing an element : O(n)

Refer this for more information on linked lists.

Feel free to comment if you have any queries.

Upvotes: 1

Related Questions