Saturday, December 2, 2023
HomeData StructuresLinked List Series #1 - Introduction - Creating a Linked list

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

-

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.

 

 

LEAVE A REPLY

Please enter your comment!
Please enter your name here

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

LATEST POSTS

00:11:41

Check Array Formation Through Concatenation | Leetcode Problem 1640

In this video, we will explain Check Array Formation Through Concatenation, Leetcode's 1640th problem in 2 different approaches along with a coding solution. Problem statement You are given...

Binary Tree Traversals in Kotlin – PreOrder, InOrder and PostOrder Traversals

Binary Tree Traversals are most common Tree Problems in an Interview as well as Competitive Programming. They can be efficient while searching, inserting and deleting...

Next Greater node in a Linked List – Leetcode Problem #1019

In this article, we will discuss the solution for 1019th Problem from Leetcode - Next Greater Node In Linked List. Let us see the question in...

Linked List Deletion – Linked List Tutorial Series #3

In this article, we will discuss about linked list deletion. We will see how to delete a node in a Singly linked list. This article will...

Follow us

1,358FansLike
10FollowersFollow
399SubscribersSubscribe

Most Popular