**What** is Linked List?

Linked List is a Linear Data Structure, Just Like the Array but in Array, Elements are stored in the Contiguous memory Location whereas in Linked List they are not stored in this manner**.**

In the linked list the elements are linked with each other using pointers. It consists of items called **“Nodes” **which contain two parts. The first part stores the actual data and the second part has a pointer that points to the next node.

The structure of a linked list is shown in the below image.

**Representation of Linked List: **

Every element in the Linked List is called a Node. A Node has a value associated with it and the pointer pointing to the next Node. Let us define a Node using struct which has an int and Node* as its data members.

This is how we define a node in C using structures or “struct”.

struct Node { int val; struct Node *next; };

Linked List with 4 Nodes.

**Operations Associated With LinkedList**

Following operations are performed on Linked List.

**Insert Node at Last**:

## C Program

```
void InsertatLast(int x) {
struct Node * temp;
temp = (struct Node * ) malloc(sizeof(struct Node));
temp -> val = x;
temp -> next = NULL;
if (head == NULL) {
head = temp;
tail = temp;
} else {
tail -> next = temp;
tail = tail -> next;
}
}
```

**Time Complexity:** O(N)

**Space Complexity:** O(1)

### Insert Node at First:

**Code:**

## C Program

```
void InsertatFirst(int x) {
struct Node * temp = (struct Node * ) malloc(sizeof(struct Node));
temp -> val = x;
temp -> next = NULL;
if (head == NULL) {
head = temp;
tail = temp;
} else {
temp -> next = head;
head = temp;
}
}
```

**Time Complexity:** O(1)

**Space Complexity:** O(1)

### Insert Node at any position:

**Code:**

## C Program

```
void InsertAfter(int pos, int x) {
struct Node * temp = (struct Node * ) malloc(sizeof(struct Node));
temp -> val = x;
temp -> next = NULL;
int len = Length();
if (pos > len) {
printf("Pos is Invalid\n");
printf("Linked List is having only %d Nodes \n", len);
return;
}
struct Node * curr = head;
while (--pos)
curr = curr -> next;
temp -> next = curr -> next;
curr -> next = temp;
}
```

**Time Complexity:** O(N)

**Space Complexity:** O(1)

### Delete Node at any Position:

**Code:**

## C Program

```
void Delete(int pos) {
int len = Length();//it gives the length of the linked list
if (pos > len) {
printf("Position is Invalid\n");
printf("Linked List is having only %d Nodes \n", len);
return;
} else if (pos == 1) {
struct Node * temp = head;
head = temp -> next;
temp -> next = NULL;
free(temp);
} else {
struct Node * curr = head, * prev = NULL;
int loc = pos;
while (--loc) {
prev = curr;
curr = curr -> next;
}
prev -> next = curr -> next;
curr -> next = NULL;
free(curr);
if (pos == len)
tail = prev;
}
}
```

**Time Complexity:** O(N)

**Space Complexity:** O(1)

### Display Node values:

**Code:**

## C Program

```
void Traverse() {
struct Node * curr = head;
printf("[ ");
if (curr == NULL) {
printf("Linked List is empty\n");
return;
}
while (curr != NULL) {
printf("%d ", curr -> val);
curr = curr -> next;
}
printf(" ]");
printf("\n");
}
```

**Time Complexity:** O(N)

**Space Complexity:** O(1)

### Length of the Linked List:

**Code:**

## C Program

```
int Length() {
int nodescount = 0;
struct Node * curr = head;
for (; curr != NULL; curr = curr -> next)
nodescount++;
return nodescount;
}
```

**Time Complexity:** O(N)

**Space Complexity:** O(1)

### Reverse Linked List:

**Code:**

## C Program

```
void ReverseList() {
struct Node * third = NULL, * second = NULL, * first = head;
while (first) {
third = second;
second = first;
first = first -> next;
second -> next = third;
}
tail = head;
head = second;
}
```

**Time Complexity:** O(N)

**Space Complexity:** O(1)

### Search for Value in Linked List:

**Code:**

## C Program

```
struct Node * SearchForValue(int x) {
struct Node * curr = head;
while (curr) {
if (curr -> val == x)
return curr;
curr = curr -> next;
}
return NULL;
}
```

**Time Complexity:** O(N)

**Space Complexity:** O(1)

Special thanks toSaiSri Angajalafor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,please check out this article