#005 DS&A - Linked List
Tags: datastructures, algorithms
Published: 2020-08-28 19:37:44

# Introduction

Nothing to say more than hello 👋,
In Case your wondering who is this man in the banner it's the Khwarizmi the inventor of algorithms concept.
Make sure to follow because I will start more advanced series in future.

## Linked List

### Single Linked List

```C
struct node
{
    char data;
    struct node *next;
}
```

self reference structures we talk about them before.

![image-20200828103740415](https://i.loli.net/2020/08/28/tjQoaqgiBmR9ywk.png)

first element is called head.

arrays are dynamic access , while linked lists are sequential accessible , it mean you need to visit all the previous element in order to reach the element you need , it mean `O(n)` while arrays are `O(1)`

searching in both will take `O(n)` .

```c
struct node *p;
p = head->next->next; // 30
p->next->next->next=p; // 50 will link to 30 , so 60 is lost
head->next=p->next; // 10 will link to 40
printf("%c" , head->next->next->next->next->data); // d
```

****

This linked list is same for all the followings. We are assuming that our linked list have more than 1 node , if it is 1 node we should put conditions to make sure that if our linked list can perform certain things.

![image-20200828104846860](https://i.loli.net/2020/08/28/s3VXkyCtZPTLRzl.png)

### Traversing a single linked list

```c
struct node *t;
t = head;
while(t != NULL) { // or while(t) have same meaning
    printf("%d\n" , t->data);
	t=t->next;
}
```

we are using `t` because if we lost the head , it's mean we lost the entire node.

### Inserting an element in single linked list

```c
struct node* new = (struct node*)malloc(sizeof(struct node))
```

this is will create a pointer called new

a) insert at beginning :

```c
new->next=head;
head = new;
```

b) insert at the end

```c
while(t->next != NULL) {
    t=t->next;
}
t->next = new;
new->next = NULL;
```

c) insert a node at specific element

```c
struct node
{
    int i;
    struct node *next;
}
// asume we need to insert after node 2
while(t->i != 2) 
{
    t = t->next;
}
new->next = t->next;
t->next = new;
```

### Deleting a node from single linked list

`malloc` will create a space for us while `free` will free the memory that we got it from `malloc`

```c
// assume we are resetting the linked list to it's init state
// deleting a node from the head
head = head->next;
free(t);
// deleting a node from the tail
while(t->next->next != NULL) {
    t = t->next;
}
free(t->next);
t->next=NULL;
// delete a specific node
while(t->next->i != 3){
    t = t->next;
}
struct node *t1 = t->next;
t->next = t1->next; // or t->next->next
free(t1);
```

### example 1

```c
struct node
{
    int val;
    struct node *next;
};

void rearrange(struct node *list)
{
    struct node *p , *q;
    int temp;
    if(!list || !list->next) return; // if linkedlist have no or 1 element return
    p = list; q=list->next; // q pointing to 1st element and q to second
    while(q) // while q is not null do
    {
        temp = p->val;p->val=q->val;
        q->val=temp;p=q->next; // swap q and p
        q=p?p->next:0; // if p is pointing to something it will take it otherwise 0
    }
}
// output : 2 1 4 3 6 5 7
```

### printing the elements using recursion

```c
// print then recursion
void f(struct node *p)
{
    if(p)//1
    {//2
        printf("%d" , p->data);//3
        f(p->link);//4
    }//5
}
// output : 1 2 3 4
```

It will print before start go into next stack

![image-20200828120742122](https://i.loli.net/2020/08/28/eKO6Xtr4YPhHgWd.png)

when it's go back it will return to line 5

![image-20200828120836003](https://i.loli.net/2020/08/28/h3FcojkTBnJ8Psq.png)

```c
// recursion then print === print in reverse order
void f(struct node *p)
{
    if(p)//1
    {//2
        f(p->link);//3
        printf("$d" , p->data);//4
    }//5
}

// output : 4 3 2 1
```

![image-20200828120928007](https://i.loli.net/2020/08/28/4S9nF8TCIoWwmzV.png)

then when it go back it will start at line 4 which printing the value of p stored inside of each stack

![image-20200828121009197](https://i.loli.net/2020/08/28/NZE4LGb8lwQB61m.png)

### Reversing an single linked list using iteration

```c
struct node
{
    int i;
    struct node * next;
}
struct node * reverse(struct node * cur)
{
    struct node *prev = NULL,*nextNode = NULL;
    while(cur)
    {
        nextNode = cur->next;
        cur->next=prev;
        prev=cur;
        cur=nextNode;
    }
    return prev;
}
```

### Reversing an single linked list using recursion

```c
struct node *head;
void reverse(struct node *prev , struct node *cur)
{
    if(cur)
    {
        reverse(cur , cur->next);
        cur->next = prev;
    } else 
        head = prev;
}

void main()
{
    //...
    reverse(NULL , head);
    //..
}
```

### circular Linked List

circular linked list have it's tail pointing to sentinel which is the head but containing the number of nodes instead with pointer to first element.

![image-20200828222532882](https://i.loli.net/2020/08/29/dqzmLt2uBQYwe98.png)

```c
while(p->next != head){}
```

### double linked list

![image-20200828222931943](https://i.loli.net/2020/08/29/l54SZnRKwiou2JT.png)

```c
// insert at start
struct node {
    int i;
    struct node *prev;
    struct node *next;
};
t->next = head;
head = t;
t->prev = NULL;
head->next->prev = head;

// insert at the end
while(p->next) p = p->next;
p->next=t;
t->prev=p;
t->next=NULL;

// insert between > 1 and < n where n is number of node
t->prev=p; // p is the pointer of the element previous to t
t->next=p->next;
p->next=t;
t->next->prev=t;
```