Search

Home /

#### Related Tutorials

A linked list is a linear data structure. In the Linked list, we connect some nodes one after another. Every node consists of the value and address of other nodes.

We will learn Linked list with a Singly linked list, then we will learn about other types of linked lists in next tutorial.

## Represent of Singly Linked List

Linked List is represented with custom data types we will say nodes.
Every node consists

• Data

## Singly Linked List representation with C++

```// Creating a node
class Node {
public:
int value;
Node* next;
};
```

Let’s create three node and set value 1, 2 and 3 respectively.

```Node* head;
Node* one = NULL;
Node* two = NULL;
Node* three = NULL;

// allocate 3 nodes in the heap
one = new Node();
two = new Node();
three = new Node();

// Assign value values
one->value = 1;
two->value = 2;
three->value = 3;
```

Now we have to link those one after another.

```// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;
```

Now this linked list look likes

If we merge this together.

```// Linked list implementation in C++

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

// Creating a node
class Node {
public:
int value;
Node* next;
};

int main() {
Node* one = NULL;
Node* two = NULL;
Node* three = NULL;

// allocate 3 nodes in the heap
one = new Node();
two = new Node();
three = new Node();

// Assign value values
one->value = 1;
two->value = 2;
three->value = 3;

// Connect nodes
one->next = two;
two->next = three;
three->next = NULL;

// print the linked list value
}
}
```

```# Linked list implementation in Python

class Node:
# Creating a node
def __init__(self, item):
self.item = item
self.next = None

def __init__(self):

if __name__ == '__main__':

# Assign item values
second = Node(2)
third = Node(3)

# Connect nodes
second.next = third

# Print the linked list item

```

## Insertion in Singly Linked List

Time complexity of inserting new node in singly linked list is O(1).
Suppose we have a new node “a” , we want to insert it after the node “b”. To insert this, assign node b’s next node to a’s next node. Then assign a to b node’s next node.

```a->next = b->next
b->next=a
```

## Deletion in Singly Linked List

Time complexity of deletion is also O(1) if we know the previous node. but if we don’t know the previous node, then first we have to search for previous which is in worst case O(n) complexity.
Suppose we have a node currentNode and previous node of this node is prevNode. Now we want to delete currentNode.

```prevNode->next=currentNode->next
```

#### Check Our Ebook for This Online Course

Advanced topics are covered in this ebook with many practical examples.