# Introduction to Linked Lists

## What are Linked Lists?

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:

1.  Singly Linked Lists
2.  Doubly Linked Lists
3.  Circular 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.

![](https://res.cloudinary.com/dlomjljb6/image/upload/v1/media/blog/uploads/2022/07/07/linkedlist%5Fgrnuah)

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.

## Arrays vs Linked Lists

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`.

```py
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:

```py
class SinglyLinkedList:
    def __init__(self):
        self.head = None

```

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.

Stay tuned, thanks for reading!