Linked List, like arrays, is an example of Linear data structure. While linked lists are not a popular day to day data structures, they have some advantages compared to other data types like arrays.
Agenda of this article
By the end of this article, We will know about – what are the advantages and disadvantages of linked lists, how to create a node and how to create a simple linked list by connecting nodes using Python programming language.
What is a Linked List?
Before knowing what are linked lists, let us know what is a node.
Node
A node is a part of linked list which consists of two things – data and pointer / address to next node.
Linked List
A linked list is a Linear data structure which consists of chain of nodes each addressing to one another. The first element of Linkedlist is usually considered as head. The last element of the linkedlist refers to null meaning that the linkedlist terminates at that node.
Advantages:
- Linked lists doesn’t need pre-memory allocation
- While arrays has fixed block, linked list’s each node can be anywhere in memory.
Disadvantages:
- Linked lists can take O(N) time to find an element in the worst case where as arrays takes only O(1) time.
- Linked lists are hard to manipulate.
- They waste memory in terms of extra reference points.
Related links:
Let us see how a Node looks like in Python:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Node: | |
| def __init__(self, data): | |
| self.data = data # assigning the data passed | |
| self.next = None # initializing the node as null |
Creation of Linked Lists
Now let us see how we can create a linked list of size 3 and how each node is connected to one another in Python. The code is commented wherever it is necessary.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Node: | |
| def __init__(self, data): | |
| self.data = data # assigning the data passed | |
| self.next = None # initializing the node as null | |
| class LinkedList: | |
| def __init__(self): | |
| self.head = None | |
| # actual code execution starts from here | |
| if __name__ == '__main__': | |
| linkedList = LinkedList() | |
| linkedList.head = Node('a') # pointed linkedlist's head to node 'a' | |
| second = Node('b') # created a simple new second node | |
| third = Node('c') # created a simple new third node | |
| ''' | |
| We created 3 nodes as follows: | |
| llist.head second third | |
| | | | | |
| | | | | |
| +—-+——+ +—-+——+ +—-+——+ | |
| | 1 | None | | 2 | None | | 3 | None | | |
| +—-+——+ +—-+——+ +—-+——+ | |
| ''' | |
| # now linking second node to linked list's head node | |
| linkedList.head.next = second | |
| ''' | |
| Now next of first Node refers to second. So they | |
| both are linked. | |
| llist.head second third | |
| | | | | |
| | | | | |
| +—-+——+ +—-+——+ +—-+——+ | |
| | 1 | o——–>| 2 | null | | 3 | null | | |
| +—-+——+ +—-+——+ +—-+——+ | |
| ''' | |
| # linking third node to second node | |
| second.next = third | |
| ''' | |
| Now next of second Node refers to third. So all three | |
| nodes are linked. | |
| llist.head second third | |
| | | | | |
| | | | | |
| +—-+——+ +—-+——+ +—-+——+ | |
| | 1 | o——–>| 2 | o——–>| 3 | null | | |
| +—-+——+ +—-+——+ +—-+——+ | |
| ''' |
In lines 15 to 17, we are linking all the nodes to form a Linkedlist.
Traversing through Linked Lists
Now let us traverse through our three nodes and print the data inside them.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Node: | |
| def __init__(self, data): | |
| self.data = data # assigning the data passed | |
| self.next = None # initializing the node as null | |
| class LinkedList: | |
| def __init__(self): | |
| self.head = None | |
| def traverse(self): | |
| node = self.head | |
| while node is not None: | |
| print(node.data) | |
| node = node.next | |
| # actual code execution starts from here | |
| if __name__ == '__main__': | |
| linkedList = LinkedList() | |
| linkedList.head = Node('a') | |
| second = Node('b') | |
| third = Node('c') | |
| linkedList.head.next = second | |
| second.next = third | |
| linkedList.traverse() |
In the next article, we will discuss about singly linked list’s insertion and deletion. In case of any queries/ discussions, please use comment box below.
