Skip to content

Linked List📃

List📌

question: can’t I do it with arrays?

  • empty list has size 0
  • insert/remove/count
  • read/modify
  • specify data-type

When array is full, create a new larger array ,copy previous array into the new array.

free the memory of the previous array

  1. Access-read/write –O(1)
  2. Insert/remove/add – O(n)

Linked List📌

list.svg

1
2
3
4
struct Node{
    int data;   //4 bytes
    Node *next; //4 bytes
}

address of the head node gives us the access to the complete list

  1. Access to element –O(n)
  2. Insert/remove/add – O(n)

Array vs Linked List📌

  • Array Linked List
    1)Cost of accessing an element constant time–O(1) Average case–O(n)
    2)Memory usage fixed size no unused memory
    memory may not be available as a large block extra memory for pointer variables
    memory may be available as multiple small blocks
    3)Cost of inserting/deleting an element a) at beginning -O(n) a)-O(1)
    b)at end -O(1) b)-O(n)
    4)Easy to use ✔️ ❌

Implementation in C/C++(singly-linked list)📌

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Node *A;
A=NULL;//empty list
Node *temp=(*Node)malloc(sizeof(Node));//C
Node *temp=new Node();//C++
(*temp).data=2;
//OR
temp->data=2;

(*temp).link=NULL;
//OR
temp->link=NULL;
A=temp;

‼️Basics：Traversal of the list📌

1
2
3
while(temp1->link!=NULL){
    temp1=temp1->link;
}

1）Insert in the beginning📌

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//Insert in the beginning
struct Node {
    int data;
    Node* next;
};


struct Node*head;//global variable


void Insert(int x) {
    struct Node *temp=(Node*)malloc(sizeof(struct Node));
    //or---------
    Node *temp=new Node();//C++
    //-------------
    temp->data=x;
    temp->next=head;
    head=temp;
}
void Print() {
    struct Node* temp=head;
    printf("List is:");
    while(temp!=NULL) {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}

int main(){
    head=NULL;//empty list
    printf("How many numbers?");
    int n,i,x;
    scanf("%d",&n);
    for(i=0;i<n;i++) {
        printf("Enter number:");
        scanf("%d",&x);
        Insert(x);
        Print();
    }
}

2）Insert in the middle📌

list-insert-1.svg list-insert-2.svg list-insert-3.svg

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct Node {
    int data;
    Node*next;
};

struct Node*head;//pointer to the head

void Insert(int data,int n);
void Print();

int main() {
    head=NULL;      //empty list
    Insert(2,1);    //List:2
    Insert(3,2);    //List:2,3
    Insert(4,1);    //list:4,2,3
    Insert(5,2);    //List:4,5,2,3
    Print();
}
//-------------------------------------------------------------------------------------------
void Insert(int data,int n) {
    Node *temp1=new Node();
    temp1->data=data;
    temp1->next=NULL;
    if(n==1) {//in case to insert in the beginning
        temp1->next=head;
        head=temp1;
        return;
    }
    Node *temp2=head;//temp2 is an aid for finding the position
    for(int i=0;i<n-2;i++) {
        temp2=temp2->next;
    }//go to the n-1 node
    temp1->next=temp2->next;
    temp2->next=temp1;
}
//-------------------------------------------------------------------------------------------
void Print() {
    Node *temp=head;
    while(temp!=NULL) {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}

image-20241017185651616

3）Delete in a list📌

  • fix the links
  • free the space from memory
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
struct Node {
    int data;
    Node*next;
};
struct Node*head;                  //global

void Insert(int data);              //insert at the end of the list
void Print();                       //print all the elements in the list
void Delete(int n);                 //delete node at position n

int main() {
    head = NULL;
    Insert(2);
    Insert(4);
    Insert(6);
    Insert(5);          //List:5,6,4,2
    int n;
    printf("Enter a position:\n");
    scanf("%d", &n);
    Delete(n);
    Print();
}

//-------------------------------------------------------------------------------------------

void Delete(int n) {
    Node*temp1=head;
    int i;
    if(n==1) {
        head=temp1->next;
        free(temp1);
        return;
    }

    for(i=0;i<n-2;i++) {
        temp1=temp1->next;
    }                               //temp1 points to the (n-1)th node
    struct Node*temp2=temp1->next;
    temp1->next=temp2->next;
    free(temp2);                    //delete temp2
}
//-------------------------------------------------------------------------------------------

void Insert(int x) {
    struct Node *temp=new Node();
    temp->data=x;
    temp->next=head;
    head=temp;
}
void Print() {
    Node*temp=head;
    while(temp!=NULL) {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}

4）Reverse a linked list📌

image-20241018104750434

①Iteration way📌

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void Reverse() {
    Node *next,*prev,*current;
    current=head;
    prev=NULL;
    while(current!=NULL) {
        next=current->next;
        current->next=prev;
        prev=current;
        current=next;
    }
    head=prev;
}

e.g.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct Node {
    int data;
    Node* next;
};

struct Node* head;

struct Node* Insert(Node* head, int data);
void Print(Node* head);
struct Node* Reverse(Node* head);

int main() {
    head = NULL;
    head = Insert(head, 2);
    head = Insert(head, 4);
    head = Insert(head, 6);
    head = Insert(head, 8);
    head = Reverse(head);
    Print(head);
}

struct Node* Insert(Node* head, int data) {
    Node* temp = new Node();
    temp->data = data;
    temp->next = NULL;

    if (head == NULL) {
        head = temp;
    } else {
        Node* current = head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = temp;
    }
    return head;
}

void Print(Node* head) {
    while (head != NULL) {
        std::cout << head->data << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

struct Node* Reverse(Node* head) {
    Node* next = NULL;
    Node* prev = NULL;
    Node* current = head;

    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    head = prev;
    return head;
}

②Recursion way to print📌

Tip

Recursion is like calling or using itself in the function

Normal print 

1
2
3
4
5
6
7
void Print(struct Node* p) {
    //recursion
    //2 6 5 4
    if(p==NULL) return;           //Exit Recursion, prevent dead loop
    printf("%d ",p->data);  //First print the value int the node
    Print(p->next);               //Recursive call
}

Reverse print

1
2
3
4
5
6
7
void ReversePrint(struct Node* q) {
    //recursion
    //4 5 6 2
    if(q==NULL) return;           //Exit Recursion
    ReversePrint(q->next);               //First do a Recursive call
    printf("%d ",q->data);  //print the value int the node
}

e.g.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct Node {
    int data;
    Node*next;
};

struct Node* Insert(Node* head, int data) {
    Node *temp=new Node;
    temp->data = data;
    temp->next = NULL;
    if (head == NULL) {
        head = temp;
    } else {
        Node *current = head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = temp;
    }
    return head;
}


void Print(struct Node* p) {
    //recursion
    //2 6 5 4
    if(p==NULL) return;           //Exit Recursion
    printf("%d ",p->data);  //First print the value int the node
    Print(p->next);               //Recursive call
}

void ReversePrint(struct Node* q) {
    //recursion
    //4 5 6 2
    if(q==NULL) return;           //Exit Recursion
    ReversePrint(q->next);               //First do a Recursive call
    printf("%d ",q->data);  //print the value int the node
}

int main() {
    struct Node* head = NULL;//local variable,empty list 
    head = Insert(head,2);
    head = Insert(head,4);
    head = Insert(head,6);
    head = Insert(head,5);
    Print(head);
    printf("\n");
    ReversePrint(head);
}

image-20241018130753641

Recursion tree

③Recursion way📌

image-20241018104750434

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
struct Node*head;//global
void Reverse(struct Node*p) {
    if(p->next==NULL) {             //exit condition
        head=p;
        return;
    }
    Reverse(p->next);
    //make reverse link
    Node *q=p->next;
    q->next=p;
    p->next=NULL;
}

Tip

1
2
3
4
Node *q=p->next;
q->next=p;
//can also be written as 
p->next->next=p

Doubly Linked List📌

list.svg

singly linked list

Doubly linked list

  • one link to the previous and one link to the next

1
2
3
4
5
struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
};
double-list.svg

doubly linked list

Important

pros cons
Reverse look-up Extra memory for pointer to the previous node

Implementation in C/C++(doubly-linked list)📌

wrong-way.png

wrong way

  • The problem with using the “&” operator: The stack frame of GNN will be reclaimed and even if you have the address of e.g. 50, you won't be able to get it.->It doesn't create anything in the heap.

  • The only way to access something in heap is through a pointer.

right-way.png

right way

Create new Node

1
2
3
4
5
6
7
struct Node *GetNewNode(int x) {
    Node *newNode=new Node;
    newNode->data=x;
    newNode->prev=NULL;
    newNode->next=head;
    return newNode;
}

Insert Ahead

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void InsertAhead(int x) {
    struct Node *newNode = GetNewNode(x);   //the newNode here is a local variable different from the one in the function GetNewNode,just share the same name
    if(head==NULL) {//when list is empty
        head=newNode;
        return;
    }
    head->prev=newNode;
    newNode->next=head;
    head=newNode;
}

Normal print/Reverse print

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void Print() {
    Node* temp=head;
    printf("Forward:");
    while(temp!=NULL) {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}

void ReversePrint() {
    Node *temp=head;
    if(temp==NULL) return;//empty list,exit
    //Going to last node
    while(temp->next!=NULL) {
        temp=temp->next;
    }
    //traversing backward using prev pointer
    printf("Reverse :");
    while(temp!=NULL) {
        printf("%d ",temp->data);
        temp=temp->prev;
    }
    printf("\n");
}

e.g.

1
2
3
4
5
6
7
8
//using the functions upon…… 
int main() {
    head=NULL;
    InsertAhead(2);Print();ReversePrint();
    InsertAhead(3);Print();ReversePrint();
    InsertAhead(4);Print();ReversePrint();
    InsertAhead(5);Print();ReversePrint();
}