Data Structures Data Structures References

# Data Structure - Linked List

A linked list is a linear data structure, in which the elements are stored in the form of a node. Each node contains two sub-elements. A data part that stores the value of the element and next part that stores the pointer to the next node as shown in the below image: The first node also known as HEAD is always used as a reference to traverse the list. The last node points to NULL. Linked list can be visualized as a chain of nodes, where every node points to the next node. The types of linked list are mentioned below:

• Singly Linked List: can be traversed only in forward direction.
• Doubly Linked List: can be traversed in forward and backward directions.
• Circular Singly Linked List: Last element contains link to the first element as next.
• Circular Doubly Linked List: Last element contains link to the first element as next and the first element contains link of the last element as previous.

## Implementation of Singly Linked List

### Representation:

In C, a node can be created using structure. In C++, singly linked list can be created using a class and a Node using structures. The LinkedList class contains Node as class member.

In Java, Python, C# and PHP, singly linked list can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.

```//node structure
struct Node {
int data;
Node* next;
};

public:
public:
//constructor to create an empty LinkedList
}
};
```
```//node structure
struct Node {
int data;
struct Node* next;
};
```
```# node structure
class Node:
#constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None

#constructor to create an empty LinkedList
def __init__(self):
```
```//node structure
class Node {
int data;
Node next;
};

//constructor to create an empty LinkedList
}
};
```
```//node structure
class Node {
public int data;
public Node next;
};

//constructor to create an empty LinkedList
}
};
```
```//node structure
class Node {
public \$data;
public \$next;
}

//constructor to create an empty LinkedList
public function __construct(){
}
};
```

### Create a Singly Linked List

Let us create a simple singly linked list which contains three data nodes.

```#include <iostream>
using namespace std;

//node structure
struct Node {
int data;
Node* next;
};

public:
public:
//constructor to create an empty LinkedList
}
};

// test the code
int main() {

Node* first = new Node();
first->data = 10;
first->next = NULL;

Node* second = new Node();
second->data = 20;
second->next = NULL;
first->next = second;

Node* third = new Node();
third->data = 30;
third->next = NULL;
second->next = third;

return 0;
}
```
```#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
int data;
struct Node* next;
};

// test the code
int main() {
//create the head node with name MyList
struct Node* MyList = NULL;

struct Node* first;
//allocate second node in the heap
first = (struct Node*)malloc(sizeof(struct Node));
first->data = 10;
first->next = NULL;
MyList = first;

struct Node* second;
//allocate second node in the heap
second = (struct Node*)malloc(sizeof(struct Node));
second->data = 20;
second->next = NULL;
first->next = second;

struct Node* third;
//allocate third node in the heap
third = (struct Node*)malloc(sizeof(struct Node));
third->data = 30;
third->next = NULL;
second->next = third;

return 0;
}
```
```# node structure
class Node:
#constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None

#constructor to create an empty LinkedList
def __init__(self):

# test the code

first = Node(10)

second = Node(20)
first.next = second

third = Node(30)
second.next = third
```
```//node structure
class Node {
int data;
Node next;
};

//constructor to create an empty LinkedList
}
};

// test the code
public class Implementation {
public static void main(String[] args) {

Node first = new Node();
first.data = 10;
first.next = null;

Node second = new Node();
second.data = 20;
second.next = null;
first.next = second;

Node third = new Node();
third.data = 30;
third.next = null;
second.next = third;
}
}
```
```using System;

//node structure
class Node {
public int data;
public Node next;
};

//constructor to create an empty LinkedList
}
};

// test the code
class Implementation {
static void Main(string[] args) {

Node first = new Node();
first.data = 10;
first.next = null;

Node second = new Node();
second.data = 20;
second.next = null;
first.next = second;

Node third = new Node();
third.data = 30;
third.next = null;
second.next = third;
}
}
```
```<?php
//node structure
class Node {
public \$data;
public \$next;
}

//constructor to create an empty LinkedList
public function __construct(){
}
};

// test the code

\$first = new Node();
\$first->data = 10;
\$first->next = null;

\$second = new Node();
\$second->data = 20;
\$second->next = null;
\$first->next = \$second;

\$third = new Node();
\$third->data = 30;
\$third->next = null;
\$second->next = \$third;
?>
```

### Traverse a Singly Linked List

A singly linked list can be traversed using a temp node. Keep on moving the temp node to the next one and displaying its content. At the end of the list, the temp node will become NULL.

```#include <iostream>
using namespace std;

//node structure
struct Node {
int data;
Node* next;
};

public:
public:
//constructor to create an empty LinkedList
}

//display the content of the list
void PrintList() {
if(temp != NULL) {
cout<<"The list contains: ";
while(temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<"\n";
} else {
cout<<"The list is empty.\n";
}
}
};

// test the code
int main() {

Node* first = new Node();
first->data = 10;
first->next = NULL;

Node* second = new Node();
second->data = 20;
second->next = NULL;
first->next = second;

Node* third = new Node();
third->data = 30;
third->next = NULL;
second->next = third;

//print the content of list
MyList.PrintList();
return 0;
}
```

The above code will give the following output:

```The list contains: 10 20 30
```
```#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
int data;
struct Node* next;
};

//display the content of the list
printf("The list contains: ");
while (temp != NULL) {
printf("%i ",temp->data);
temp = temp->next;
}
printf("\n");
} else {
printf("The list is empty.\n");
}
}

// test the code
int main() {
//create the head node with name MyList
struct Node* MyList = NULL;

struct Node* first;
//allocate second node in the heap
first = (struct Node*)malloc(sizeof(struct Node));
first->data = 10;
first->next = NULL;
MyList = first;

struct Node* second;
//allocate second node in the heap
second = (struct Node*)malloc(sizeof(struct Node));
second->data = 20;
second->next = NULL;
first->next = second;

struct Node* third;
//allocate third node in the heap
third = (struct Node*)malloc(sizeof(struct Node));
third->data = 30;
third->next = NULL;
second->next = third;

//print the content of list
PrintList(MyList);
return 0;
}
```

The above code will give the following output:

```The list contains: 10 20 30
```
```# node structure
class Node:
#constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None

#constructor to create an empty LinkedList
def __init__(self):

#display the content of the list
def PrintList(self):
if(temp != None):
print("The list contains:", end=" ")
while (temp != None):
print(temp.data, end=" ")
temp = temp.next
print()
else:
print("The list is empty.")

# test the code

first = Node(10)

second = Node(20)
first.next = second

third = Node(30)
second.next = third

#print the content of list
MyList.PrintList()
```

The above code will give the following output:

```The list contains: 10 20 30
```
```//node structure
class Node {
int data;
Node next;
};

//constructor to create an empty LinkedList
}

//display the content of the list
void PrintList() {
Node temp = new Node();
if(temp != null) {
System.out.print("The list contains: ");
while(temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
} else {
System.out.println("The list is empty.");
}
}
};

// test the code
public class Implementation {
public static void main(String[] args) {

Node first = new Node();
first.data = 10;
first.next = null;

Node second = new Node();
second.data = 20;
second.next = null;
first.next = second;

Node third = new Node();
third.data = 30;
third.next = null;
second.next = third;

//print the content of list
MyList.PrintList();
}
}
```

The above code will give the following output:

```The list contains: 10 20 30
```
```using System;

//node structure
class Node {
public int data;
public Node next;
};

//constructor to create an empty LinkedList
}

//display the content of the list
public void PrintList() {
Node temp = new Node();
if(temp != null) {
Console.Write("The list contains: ");
while(temp != null) {
Console.Write(temp.data + " ");
temp = temp.next;
}
Console.WriteLine();
} else {
Console.WriteLine("The list is empty.");
}
}
};

// test the code
class Implementation {
static void Main(string[] args) {

Node first = new Node();
first.data = 10;
first.next = null;

Node second = new Node();
second.data = 20;
second.next = null;
first.next = second;

Node third = new Node();
third.data = 30;
third.next = null;
second.next = third;

//print the content of list
MyList.PrintList();
}
}
```

The above code will give the following output:

```The list contains: 10 20 30
```
```<?php
//node structure
class Node {
public \$data;
public \$next;
}

//constructor to create an empty LinkedList
public function __construct(){
}

//display the content of the list
public function PrintList() {
\$temp = new Node();
if(\$temp != null) {
echo "The list contains: ";
while(\$temp != null) {
echo \$temp->data." ";
\$temp = \$temp->next;
}
echo "\n";
} else {
echo "The list is empty.\n";
}
}
};

// test the code

\$first = new Node();
\$first->data = 10;
\$first->next = null;

\$second = new Node();
\$second->data = 20;
\$second->next = null;
\$first->next = \$second;

\$third = new Node();
\$third->data = 30;
\$third->next = null;
\$second->next = \$third;

//print the content of list
\$MyList->PrintList();
?>
```

The above code will give the following output:

```The list contains: 10 20 30
```

5