A linked list is a linear data structure. In which we can sequentially store the data. Unlike an array linked list is a dynamic data structure the size of a linked list can grow or shrink depending on the situation.
However, in the case of Arrays, we need to predefine the size and we can’t add more items than the max size defined.
More Information
The element of a linked list is called a node. Every element or node contains two main entities first entity is the information or the data whereas the second entity is the pointer to the next node.
The structure of the linked list is like a train. A linked list has the following components –
Data: Data is the value stored in it, it could be anything an integer or a string or anything else really.
Pointer (Link) – Each linked list contains a pointer which points to address of the next node in the linked list train.
Apart from this the following are also keywords used in linked lists –
Node – Any single unit of a linked list, its data and pointer(s), is called a node.
Head: First is the head who is defined the beginning of the list.
Tail: second is tail which defined end of the list.
What is a linked listLinked List like an array is a linear data structure. However, the elements or data storage of linked list elements are not in a contiguous manner and we use pointers to create linearity in linked lists.
Why we use Linked List in Data Structure?
Generally for storage arrays are used. But, there are many many disadvantaged with arrays –
1. Fixed Size
The size of the array is fixed and needs to be pre-defined
Example – int a[10]; or int a[ ] = {1, 2, 3, 4, 5}
We can’t declare an array without declaring the size.
2. Memory wastage (Not Optimised)
If you declare an array of size 10 and just assign values to first two elements
The memory is allocated to all of them even though, we may not end up using them.
3. Need for Contiguous Memory
Arrays need Contiguous memory, which some times is bad.
Example – Consider there are only three memories of size 10, 10 and 400
We need to store an array of size 15
In this case, the array will use memory location is size 400 and not combine memory A and B of size 10 and 10 respectively.
Thus wasting a lot of memory
4. Inserting in Array is expensive
Let us say you have an array a[] = {10, 20, 40, 60, 80} and we need to add 50 in the same sorted format.
Then, we have to move all elements after 40 to one additional position
Also, the same goes for deletion if we want to delete 20. Then all elements after it have to be moved to one position in the opposite direction.
Linked List in Data Structure
Advantages
Ease of insertion and deletion.
Dynamic Size
Disadvantages
We have to search elements linearly, and can’t do random access
We can’t do efficient searches like binary search
Extra space for pointers is needed
Linked lists are not cache friendly as arrays are stored in contigious format they can be cached easily
Loss of data threat is there, if we lose one pointer location the rest of linked list can’t be accessed.
class LinkedList {
Node head; // head
// Linked list Node
class Node {
int data;
Node next;
// constructor to initialize
Node(int d) {
data = d;
}
}
}
Python
# Node class
class Node:
# Function to initialize the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize
# next as null
# Linked List class
class LinkedList:
# Function to initialize the Linked
# List object
def __init__(self):
self.head = None
Doubly linked list
A doubly linked list is a kind of complex linked list, in which it contains the address of the previous node as well as the next node. A doubly linked list contains the following –
Data: The data present in the node.
Link (Previous) – A pointer to the previous node in the linked list.
Link (Next) – A pointer to the next node in the linked list
In this way, for a doubly-linked list we can travel in both directions for traversals.
struct Node {
int data;
struct Node* next, prev;
};
C++
class Node {
public:
int data;
Node* next, prev;
};
Java
class LinkedList {
Node head; // head
// Linked list Node
class Node {
int data;
Node next, prev;
// constructor to initialize
Node(int d) {
data = d;
}
}
}
Python
# Node class
class Node:
# Function to initialize the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize # next as null self.prev = None # Initialize # prev as null
# Linked List class
class LinkedList:
# Function to initialize the Linked
# List object
def __init__(self):
self.head = None
struct Node {
int data;
struct Node* next;
}; //last node will have the address of the head
C++
class Node {
public:
int data;
Node* next;
}; //last node will have the address of the head
Java
class LinkedList {
Node head; // head
// Linked list Node
class Node {
int data;
Node next;
// constructor to initialize
Node(int d) {
data = d;
}
}
} //last node will have the address of the head
Python
# Node class
class Node:
# Function to initialize the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize # next as null
# Linked List class
class LinkedList:
# Function to initialize the Linked
# List object
def __init__(self):
self.head = None //last node will have the address of the head
Linked List is one of the most crucial topics which is easy once understood thoroughly. This topic is very important for both your college semester examinations as well as for placement purposes.
Deletion from beginning in Circular Linked List – C | C++ | Java
Deletion from nth position in Circular Linked List – C | C++ | Java
Deletion from end in Circular Linked List – C | C++ | Java
Insertion and Deletion in a Circular Linked List – C | C++ | Java
Split a Circular Linked List in two halves – C | C++ | Java
Count nodes in Circular Linked List – C | C++ | Java
Sorted Insert In Circular Linked List – C | C++ | Java
Insertion in the middle in Circular Linked List – C | C++ | Java
Linked Lists
Linked List is one of the most crucial topics which is easy once understood thoroughly. This topic is very important for both your college semester examinations as well as for placement purposes.
You cannot implement Linked List in Python, as Python doesn’t have the concept of Pointers. But in Python you can use List, or other data structures like Dictionaries which may help you in storing the data efficiently
I want the materials to learn Data structures with Python.
How to implement linkedlist in java , as in java there is no concept of pointers.
Pointers are there in Java also.
Please visit this page – https://prepinsta.com/data-structures/
I hope this will resolve your query
How to solve linked list problems in python?
You cannot implement Linked List in Python, as Python doesn’t have the concept of Pointers. But in Python you can use List, or other data structures like Dictionaries which may help you in storing the data efficiently
You can implement in Python as Well !
here is the sample Code!
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = self.tail = None
def insert(self, value, location):
newNode = Node(value)
if self.head is None:
self.head = self.tail = newNode
else:
#Begining loc = 0
if location == 0:
newNode.next = self.head
self.head = newNode
elif location == 1:
self.tail.next = newNode
self.tail = newNode
else:
curNode = self.head
index = 1
while index < location:
curNode = curNode.next
index += 1
newNode.next = curNode.next
curNode.next = newNode