# Ashutosh Writes

Oct 10, 2022ยท

Linked Lists are yet another linear data structure in which the elements are not stored in contiguous memory locations. There are mainly three types of linked lists:

In general, we will be taking singly linked lists into consideration.

## Basic Structure

Every linked list consists of nodes where each node has two components - data and next pointer.

Note: The above image shows a Singly Linked List.

The data part of the node is used to store some kind of data and can be of type of string, number, or any other object type. The next part of the node is a pointer pointing from one node to its next node.

Apart from this, we have another pointer called head that points to the start of the linked list, i.e., the first node of the linked list. The head pointer helps us to traverse the linked list from the beginning.

The last node of the linked list(excluding circular linked lists) points to null, which means the linked list ends here.

Before we dive deep into linked lists and their implementations, let us quickly understand how they differ from a regular array.

##### Contiguous Memory

Arrays are stored in contiguous memory locations which allow the access time to be constant, whereas, in linked lists, nodes are not stored in contiguous memory.

##### Accessing Elements

Since arrays are indexed and stored in contiguous memory locations, it is a constant time operation to access elements in arrays. However, in the case of linked lists, to access the nth element, you need to perform O(n) operations because we need to start traversing the linked list from the head pointer to the nth element.

##### Insertion/Deletion

In the case of arrays, the insertion/deletion operations take O(n) time complexity because we need to shift all the elements of the array to the left or right depending upon the situation. However, in the case of linked lists, the insertion/deletion operations take constant time complexity as we just need to change the orientation of a few pointers only.

To summarise, here's what we have:

 Arrays Linked Lists Contiguous Memory Yes No Accessing Elements O(1) O(n) Insertion/Deletion O(n) O(1)

## Basic Implementation

Now, let us implement the Linked List and its nodes. To start with, we need to create a `Node` class with two attributes - `data` and `next`.

``````class Node:
def __init__(self, data):
self.data = data
self.next = None
``````

In the constructor of the `Node` class, we set `self.data` to the `data` that will passed while creating a `Node` object. We also set `self.next` to `None` for the time being. In the later sections, we will be changing this `self.next` attribute.

Next, we can create the Linked List class as:

``````class SinglyLinkedList:
def __init__(self):
``````

In the constructor, we set the `self.head` pointer to None for now. Later, we will point it to the first node of the linked list.

## Wrapping Up

Let us conclude this article here. In this article, we learned about Linked Lists and their basic structure and implementation. We also saw how they differ from arrays. In the upcoming parts, we will learn how to perform operations such as insertion, deletion, node swapping, merging of linked lists, etc.