A linked list is a data structure made of a chain of node objects. Each node contains a value and a pointer to the next node in the chain.
Linked lists are preferred over arrays due to their dynamic size and ease of insertion and deletion properties.
The head pointer points to the first
node, and the last element of the list points to null
. When the list is empty, the head pointer points to null
.
Linked lists in Python
Original Python does not ship with a built-in linked list data structure like the one seen in Java.
Let’s see how we can create our own implementation of a standard class-based singly linked list in Python.
1. Start with a single node
Let’s start with a single node since linking several nodes gives us a complete list. For this, we make a Node
class that holds some data
and a single pointer next
, that will be used to point to the next Node
type object in the Linked List.
# A single node of a singly linked list class Node: # constructor def __init__[self, data, next=None]: self.data = data self.next = next # Creating a single node first = Node[3] print[first.data]
2. Join nodes to get a linked list
The next step is to join multiple single nodes containing data
using the next
pointers, and have a single head
pointer pointing to a complete instance of a Linked List.
Using the head
pointer, we will be able to traverse the whole list,
even perform all kinds of list manipulations while we are at it.
For this, we create a LinkedList
class with a single head
pointer:
# A single node of a singly linked list class Node: # constructor def __init__[self, data = None, next=None]: self.data = data self.next = next # A Linked List class with a single head node class LinkedList: def __init__[self]: self.head = None # Linked List with a single node LL = LinkedList[] LL.head = Node[3] print[LL.head.data]
3. Add required methods to the LinkedList
class
Last but not least, we can add various linked list manipulation methods in our implementation.
Let’s have a look at the insertion and print methods for our LinkedList
implementation below:
# A single node of a singly linked list class Node: # constructor def __init__[self, data = None, next=None]: self.data = data self.next = next # A Linked List class with a single head node class LinkedList: def __init__[self]: self.head = None # insertion method for the linked list def insert[self, data]: newNode = Node[data] if[self.head]: current = self.head while[current.next]: current = current.next current.next = newNode else: self.head = newNode # print method for the linked list def printLL[self]: current = self.head while[current]: print[current.data] current = current.next # Singly Linked List with insertion and print methods LL = LinkedList[] LL.insert[3] LL.insert[4] LL.insert[5] LL.printLL[]
RELATED TAGS
data structures
python
linked list
node
classes
Copyright ©2022 Educative, Inc. All rights reserved
Like arrays, Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers. They include a series of connected nodes. Here, each node stores the data and the address of the next node.
Linked-List
Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have the following limitations:
- The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
- Insertion of a new element / Deletion of a existing element in an array of elements is expensive: The room has to be created for the new elements and to create room existing elements have to be shifted but in Linked list if we have the head node then we can traverse to any node through it and insert new node at the required position.
Example:
In a system, if we maintain a sorted list of IDs in an array id[] = [1000, 1010, 1050, 2000, 2040].
If we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 [excluding 1000].Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved due to this so much work is being done which affects the efficiency of the code.
Advantages of Linked Lists over arrays:
- Dynamic Array.
- Ease of Insertion/Deletion.
Drawbacks of Linked Lists:
- Random access is not allowed. We have to access elements sequentially starting from the first node[head node]. So we cannot do a binary search with linked lists efficiently with its default implementation.
- Extra memory space for a pointer is required with each element of the list.
- Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.
Types of Linked Lists:
- Simple Linked List – In this type of linked list, one can move or traverse the linked list in only one direction
- Doubly Linked List – In this type of linked list, one can move or traverse the linked list in both directions [Forward and Backward]
- Circular Linked List – In this type of linked list, the last node of the linked list contains the link of the first/head node of the linked list in its next pointer and the first/head node contains the link of the last node of the linked list in its prev pointer
Basic operations on Linked Lists:
- Deletion
- Insertion
- Search
- Display
Representation of Linked Lists:
A linked list is represented by a pointer to the first node of the linked list. The first node is called the head of the linked list. If the linked list is empty, then the value of the head points to NULL.
Each node in a list consists of at least two parts:
- A Data Item [we can store integer, strings, or any type of data].
- Pointer [Or Reference] to the next node [connects one node to another] or An address of another node
In C, we can represent a node using structures. Below is an example of a
linked list node with integer data.
In Java or C#, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.
C
struct
Node {
int
data;
struct
Node* next;
};
C++
class
Node {
public
:
int
data;
Node* next;
};
Java
class
LinkedList {
Node head;
class
Node {
int
data;
Node next;
Node[
int
d]
{
data = d;
next =
null
;
}
}
}
Python
class
Node:
def
__init__[
self
, data]:
self
.data
=
data
self
.
next
=
None
class
LinkedList:
def
__init__[
self
]:
self
.head
=
None
C#
class
LinkedList {
Node head;
class
Node {
int
data;
Node next;
Node[
int
d] { data = d; }
}
}
Javascript
var
head;
class Node
{
constructor[val] {
this
.data = val;
this
.next =
null
;
}
}
Construction of a simple linked list with 3 nodes:
C
#include
#include
struct
Node {
int
data;
struct
Node* next;
};
int
main[]
{
struct
Node* head = NULL;
struct
Node* second = NULL;
struct
Node* third = NULL;
head = [
struct
Node*]
malloc
[
sizeof
[
struct
Node]];
second = [
struct
Node*]
malloc
[
sizeof
[
struct
Node]];
third = [
struct
Node*]
malloc
[
sizeof
[
struct
Node]];
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
return
0;
}
C++
#include
using
namespace
std;
class
Node {
public
:
int
data;
Node* next;
};
int
main[]
{
Node* head = NULL;
Node* second = NULL;
Node* third = NULL;
head =
new
Node[];
second =
new
Node[];
third =
new
Node[];
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
return
0;
}
Java
class
LinkedList {
Node head;
static
class
Node {
int
data;
Node next;
Node[
int
d]
{
data = d;
next =
null
;
}
}
public
static
void
main[String[] args]
{
LinkedList llist =
new
LinkedList[];
llist.head =
new
Node[
1
];
Node second =
new
Node[
2
];
Node third =
new
Node[
3
];
llist.head.next = second;
second.next
= third;
}
}
Python
class
Node:
def
__init__[
self
, data]:
self
.data
=
data
self
.
next
=
None
class
LinkedList:
def
__init__[
self
]:
self
.head
=
None
if
__name__
=
=
'__main__'
:
llist
=
LinkedList[]
llist.head
=
Node[
1
]
second
=
Node[
2
]
third
=
Node[
3
]
llist.head.
next
=
second
second.
next
=
third
C#
using
System;
public
class
LinkedList {
Node head;
public
class
Node {
public
int
data;
public
Node next;
public
Node[
int
d]
{
data = d;
next =
null
;
}
}
public
static
void
Main[String[] args]
{
LinkedList llist =
new
LinkedList[];
llist.head =
new
Node[1];
Node second =
new
Node[2];
Node third =
new
Node[3];
llist.head.next = second;
second.next
= third;
}
}
Javascript
var
head;
class Node {
constructor[d]
{
this
.data = d;
this
.next =
null
;
}
}
var
head =
new
Node[1];
var
second =
new
Node[2];
var
third =
new
Node[3];
head.next = second;
second.next = third;
Traversal of a Linked List
In the previous program, we created a simple linked list with three nodes. Let us traverse the created list and print the data of each node. For traversal, let us write a general-purpose function printList[] that prints any given list.
We strongly recommend that you click here and practice it, before moving on to the solution.
C
#include
#include
struct
Node {
int
data;
struct
Node* next;
};
void
printList[
struct
Node* n]
{
while
[n != NULL] {
printf
[
" %d "
, n->data];
n = n->next;
}
}
int
main[]
{
struct
Node* head = NULL;
struct
Node* second = NULL;
struct
Node* third = NULL;
head = [
struct
Node*]
malloc
[
sizeof
[
struct
Node]];
second = [
struct
Node*]
malloc
[
sizeof
[
struct
Node]];
third = [
struct
Node*]
malloc
[
sizeof
[
struct
Node]];
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
printList[head];
return
0;
}
C++
#include
using
namespace
std;
class
Node {
public
:
int
data;
Node* next;
};
void
printList[Node* n]
{
while
[n != NULL] {
cout data next;
}
}
int
main[]
{
Node* head = NULL;
Node* second = NULL;
Node* third = NULL;
head =
new
Node[];
second =
new
Node[];
third =
new
Node[];
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
printList[head];
return
0;
}
Java
class
LinkedList {
Node head;
static
class
Node {
int
data;
Node next;
Node[
int
d]
{
this
.data = d;
next =
null
;
}
}
public
void
printList[]
{
Node n = head;
while
[n !=
null
] {
System.out.print[n.data +
" "
];
n = n.next;
}
}
public
static
void
main[String[] args]
{
LinkedList llist =
new
LinkedList[];
llist.head =
new
Node[
1
];
Node second =
new
Node[
2
];
Node third =
new
Node[
3
];
llist.head.next = second;
second.next
= third;
llist.printList[];
}
}
Python3
class
Node:
def
__init__[
self
, data]:
self
.data
=
data
self
.
next
=
None
class
LinkedList:
def
__init__[
self
]:
self
.head
=
None
def
printList[
self
]:
temp
=
self
.head
while
[temp]:
print
[temp.data]
temp
=
temp.
next
if
__name__
=
=
'__main__'
:
llist
=
LinkedList[]
llist.head
=
Node[
1
]
second
=
Node[
2
]
third
=
Node[
3
]
llist.head.
next
=
second
second.
next
=
third
llist.printList[]
C#
using
System;
public
class
LinkedList {
Node head;
public
class
Node {
public
int
data;
public
Node next;
public
Node[
int
d]
{
data = d;
next =
null
;
}
}
public
void
printList[]
{
Node n = head;
while
[n !=
null
] {
Console.Write[n.data +
" "
];
n = n.next;
}
}
public
static
void
Main[String[] args]
{
LinkedList llist =
new
LinkedList[];
llist.head =
new
Node[1];
Node second =
new
Node[2];
Node third =
new
Node[3];
llist.head.next = second;
second.next
= third;
llist.printList[];
}
}
Javascript
var
head;
class Node {
constructor[val] {
this
.data = val;
this
.next =
null
;
}
}
function
printList[]
{
var
n = head;
while
[n !=
null
] {
document.write[n.data +
" "
];
n = n.next;
}
}
var
head =
new
Node[1];
var
second =
new
Node[2];
var
third =
new
Node[3];
head.next = second;
second.next = third;
printList[];
Time Complexity:
Time Complexity | Worst Case | Average Case |
Search | O[n] | O[n] |
Insert | O[1] | O[1] |
Deletion | O[1] | O[1] |
Auxiliary Space: O[N]