An implementation in C

This is a personal project undertaken to implement linked lists in C, a commonly encountered data structure in the courseware for CS1101 in BS programs (DSA/ES) at IIT Madras.

List Structure

The above list structure is implemented using Nodes. A node holds a value and a pointer to the next node.\n A node is implemented using a struct with members value and next.

The head of a list is marked in blue. ‎ ‎ ‎ ‎ ‎

Deleted nodes are marked in red. ‎ ‎ ‎ ‎ ‎

The Node Type

typedef struct node{
    int value;
    struct node* next;
} Node;

The first node in a list is the head. In this project, all nodes reside in the heap.\n The first node (head) can be created as follows.

Node* head = (Node*)calloc(1,sizeof(Node));

or

Node* head;

The former places the head node in the heap with a default value of 0. Deleting the node in this case would require freeing the memory \n allocated to it.

free(head);

Examples

1

Getting started

#include <stdio.h>
#include <stdlib.h>
#include "sllist.h"

int main(void){
    Node* head = (Node*)calloc(1,sizeof(Node));
    head->value = 11;
    display(head);
    return 0;
}

output

[0]:11 -> NULL

2

Appending some nodes to a list

The append function has a return type of Node*. This is because an empty list can be represented by a NULL pointer too, in which \n case the function creates a new node with the given value and returns a pointer to the newly created node. This operation potentially \n changes the head node. Therefore, the head pointer is reassigned when the append function is called.

Node* head = (Node*)calloc(1,sizeof(Node));
head->value = 11;
for (int i = 0;i<10;i++){
    head = append(head,i*i);
}
display(head);

output

[0]:11 -> [1]:0 -> [2]:1 -> [3]:4 -> [4]:9 -> [5]:16 -> [6]:25 -> [7]:36 -> [8]:49 -> [9]:64 -> [10]:81 -> NULL

3

Dropping duplicates from a list

The drop duplicates function has a second parameter, max_duplicates which specifies the number of extra copies of a value to retain. \n If this value is 0, then each distinct value is retained only once and all copies are dropped.

Node* head = (Node*)calloc(1,sizeof(Node));
head->value = 11;
head = append(head,5);
head = append(head,5);
head = append(head,7);
head = append(head,7);
head = append(head,3);
head = append(head,5);
head = append(head,4);
head = append(head,1);
head = append(head,8);
head = append(head,2);

display(head);
drop_duplicates(head,0);
display(head);

output 1 (max_duplicates = 0)

[0]:11 -> [1]:5 -> [2]:5 -> [3]:7 -> [4]:7 -> [5]:3 -> [6]:5 -> [7]:4 -> [8]:1 -> [9]:8 -> [10]:2 -> NULL
[0]:11 -> [1]:5 -> [2]:7 -> [3]:3 -> [4]:4 -> [5]:1 -> [6]:8 -> [7]:2 -> NULL

output 2 (max_duplicates = 1)

[0]:11 -> [1]:5 -> [2]:5 -> [3]:7 -> [4]:7 -> [5]:3 -> [6]:5 -> [7]:4 -> [8]:1 -> [9]:8 -> [10]:2 -> NULL
[0]:11 -> [1]:5 -> [2]:5 -> [3]:7 -> [4]:7 -> [5]:3 -> [6]:4 -> [7]:1 -> [8]:8 -> [9]:2 -> NULL

4

Reversing a list

The reverse function has a second parameter, ttl which specifies the length of the initial n-node segment of the list to reverse. \n If this value is 0, then the entire list is reversed.

Node* head = (Node*)calloc(1,sizeof(Node));
head->value = 11;
head = append(head,5);
head = append(head,7);
head = append(head,3);
head = append(head,9);
head = append(head,4);
head = append(head,1);
head = append(head,8);
head = append(head,2);

display(head);
head = reverse(head,0);
display(head);

output 1 (ttl = 0)

[0]:11 -> [1]:5 -> [2]:7 -> [3]:3 -> [4]:9 -> [5]:4 -> [6]:1 -> [7]:8 -> [8]:2 -> NULL
[0]:2 -> [1]:8 -> [2]:1 -> [3]:4 -> [4]:9 -> [5]:3 -> [6]:7 -> [7]:5 -> [8]:11 -> NULL

output 2 (ttl = 5)

[0]:11 -> [1]:5 -> [2]:7 -> [3]:3 -> [4]:9 -> [5]:4 -> [6]:1 -> [7]:8 -> [8]:2 -> NULL
[0]:9 -> [1]:3 -> [2]:7 -> [3]:5 -> [4]:11 -> [5]:4 -> [6]:1 -> [7]:8 -> [8]:2 -> NULL

5

Sorting a list

The sort function sorts a list in ascending order of values.

Node* head = (Node*)calloc(1,sizeof(Node));
head->value = 11;
head = append(head,5);
head = append(head,7);
head = append(head,3);
head = append(head,9);
head = append(head,4);
head = append(head,1);
head = append(head,8);
head = append(head,2);

display(head);
sort(head);
display(head);

output

[0]:11 -> [1]:5 -> [2]:7 -> [3]:3 -> [4]:9 -> [5]:4 -> [6]:1 -> [7]:8 -> [8]:2 -> NULL
[0]:1 -> [1]:2 -> [2]:3 -> [3]:4 -> [4]:5 -> [5]:7 -> [6]:8 -> [7]:9 -> [8]:11 -> NULL

There are a total of 16 functions in this project. To explore them go to File > File members > Functions.

---