Linked List Series #1 – Introduction – Creating a Linked list

0
95
linked list featured logo

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 node diagram

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:
  1. Linked lists doesn’t need pre-memory allocation
  2. While arrays has fixed block, linked list’s each node can be anywhere in memory.
Disadvantages:
  1. Linked lists can take O(N) time to find an element in the worst case where as arrays takes only O(1) time.
  2. Linked lists are hard to manipulate.
  3. They waste memory in terms of extra reference points.

Related links:

Let us see how a Node looks like in Python:

class Node:
def __init__(self, data):
self.data = data # assigning the data passed
self.next = None # initializing the node as null

view raw
Node.py
hosted with ❤ by GitHub

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.

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.

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.

 

 

0 0 vote
Article Rating
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments