# 3. Linear Structures¶

A computer processes some data. Always. Now what we are interested in this chapter is the structure of the data. Typically we will study linear structures like arrays, linked lists, stacks, queues etc. The structure of data is important because it governs how we can perform insertion, deletion, update and more such operations on data. It not only governs but also how fast we will be able to do such stuff. Some languages which have big standard libraries like C++, Python, Java etc they provide many utilities data structures and most common operations as a part of it. However, since C99 is having a much smaller standard library such facilities are not there.

It is assumed that the reader i.e. you know about basics of concepts like arrays, pointers, functions and recursion. C is primarily used to implement the data structures and algorithms therefore if you do not know C then probably you would want to read this.

Some of the linear structures are linked lists, stacks and queues. We will start with linked lists. Linked lists are also simply known as lists. A list can be mathematically modeled as \(t_1, t_2, ..., t_n\) i.e. a list having n items of element type. \(t_i\) is known as node at position \(i\) where \(i\) is used to indicate the position. All the elements are of the same type.

## 3.1. Singly Linked List¶

Let us begin with singlly linked lists. When we say linked typically we mean singly linked list. There is other types as well. Doubly linked lists and circular linked list for example. For now we will start with singly linked list because it is simplest to understand and can be used for as a base data structure to implement stacks and queues which are going to be coming chapters. A singly linked list looks something like given below:

A linked list’s first element is typically known as `head`

and last element is
known as `tail`

. All nodes have a pointer which points to next node so that
you can traverse list in forward direction. Note that it is impossible
to traverse in opposite direction. tail’s next pointer point to NULL which
indicates the ending point of the linked list. `tail`

is not mandatory to
have when dealing with linked list but a pointer to `head`

is aleways present.

Impementation of a linked list involved a self referencing structure. Given below is a typical self referencing structure:

```
struct S {
struct S *next;
};
struct S* head;
```

The presence of `next`

which is a pointer of C causes some meory to be wasted
in linear order equal to number of nodes in linked list.
Note that real implementations will have some data members as well. Some common
operation on a linked list are insertion at beginning, in between somewhere
and at the end. We also can have an operation for counting number of nodes.
Deletion and searching of a node is also there. Note that to do any of these
operations except insertion at beginning we need to search the appropriate node
which is an operation involving traversal of list in linear fashion. Therefore
time compexity of all such operations is \(O(n)\). Insertion at beginning
will have \(O(1)\) time complexity. However, if search operation for a
particular node is to be considered separate then deletion and insertion at
any place will have time complexity of \(O(n)\).

Let us implement a linked list and its operations:

```
#include <stdio.h>
#include <stdlib.h>
typedef struct linked_list {
int data;
struct linked_list *next;
}ll;
void menu();
void add_at_beg(ll**);
void print(ll*);
void search(ll*);
void delete(ll**);
void append(ll**);
void add_in_bet(**);
void delete(ll** head)
{
ll *temp, *q;
int i;
temp = *head;
if(*head == NULL) {
printf("There is no element to be deleted.\n");
return;
}
printf("Enter the value of data to be deleted.\n");
scanf("%d", &i);
if(temp->data == i) {
*head = temp->next;
free(temp);
return;
} else {
while(temp->next != NULL) {
if(temp->data == i) {
q->next = temp->next;
free(temp);
return;
}
q = temp;
temp = temp->next;
}
}
if(temp->data == i) { // case of deletion of last node
q->next = temp->next;
free(temp);
return;
}
printf("The element to be deleted was not found.\n");
}
int count(ll* head)
{
int count = 1;
if(head == NULL) {
printf("The no. of elements in linked list is %d.\n", 0);
return 0;
}
while(head->next != NULL) {
count++;
head = head->next;
}
printf("The no. of elements in linked list is %d.\n", count);
return count;
}
void menu()
{
puts("1. Add an element at beginning.");
puts("2. Add an element at position n.");
puts("3. Add an element at end.");
puts("4. Count the number of elements.");
puts("5. Delete an element.");
puts("6. Search an element.");
puts("7. Print the list.");
}
void append(ll** head)
{
ll* temp, *q = *head;
int i;
printf("Enter the number which is to be appended to the list.\n");
scanf("%d", &i);
temp = (ll*)malloc(sizeof(ll));
temp->data = i;
temp->next = NULL;
if(!(*head)) {
*head=temp;
return;
}
while(q->next != NULL) {
q = q->next;
}
q->next = temp;
}
void add_in_bet(ll** head)
{
ll *temp, *q = *head;
int i = 0, j = 0;
int position = 0;
printf("Enter position at which the number is to be added.\n");
scanf("%d", &position);
if(position == 0)
return add_at_beg(head);
temp = (ll*)malloc(sizeof(ll));
printf("Enter an integer to be added in between.\n");
scanf("%d", &i);
while(q->next != NULL) {
++j;
if(j == position) {
temp->next = q->next;
q->next = temp;
temp->data = i;
return;
}
q = q->next;
}
++j;
// This is the case when q->next is NULL so it is an append
// operation
if(j == position) {
append(head);
}
free(temp); // no insertion happened so we need to free temp
// i.e. j was out of possible positions
}
void add_at_beg(ll** head)
{
ll *temp;
int i;
temp = (ll*)malloc(sizeof(ll));
printf("Enter an integer to be added at beginning\n");
scanf("%d", &i);
temp->next = *head;
*head = temp;
(*head)->data = i;
}
void print(ll* head)
{
printf("Head-->");
while(head != NULL) {
printf("%d--->", head->data);
head = head->next;
}
printf("NULL\n");
}
void search(ll* head)
{
int i=0, position=1;
printf("Enter the number to be searched.");
scanf("%d", &i);
while(head != NULL) {
if(head->data == i) {
printf("%d is found at %dth position.\n", i, position - 1);
return;
}
head = head->next;
position++;
}
printf("%d was not found in linked list.\n", i);
}
int main()
{
ll* head = NULL;
int option = 0;
menu();
printf("Enter 1 to 7 to choose an action. Any other number to quit.\n");
scanf("%d", &option);
getchar(); // to remove \n
while(option >= 1 && option <= 7) {
switch(option) {
case 1:
add_at_beg(&head);
break;
case 2:
add_in_bet(&head);
break;
case 3:
append(&head);
break;
case 4:
count(head);
break;
case 5:
delete(&head);
break;
case 6:
search(head);
break;
case 7:
print(head);
break;
default:
break;
}
menu();
printf("Enter 1 to 7 to choose an action. Any other number to quit.\n");
fflush(stdin);
scanf("%d", &option);
getchar(); // to remove \n
}
return 0;
}
```

Now I will explain these function one by one using images. First we discuss
`add_at_begin`

. Note that we can wrap all insertion functions by calling single
insert function of the type `insert(ll* head, int item, size_t position)`

.
Please note that I have used `size_t`

for position
because I want the list to be able to have as many members as malloc allows.
If we use something like `int`

which is nothing but `signed int`

then we would
be restricted to 2 * 1024 * 1024 * 1024 or 2147483648 members. Note that
`size_t`

is nothing but `unsigned long`

which is 4 bytes on 32-bit systems and
8 bytes
on 64-bit systems.

### 3.1.1. Insertion at the Beginning¶

Insertion at beginning is simple. We create a new node. Then we make its `next`

pointer to point to current head and then use current head pointer to point to
this new node. The entire operation is shown graphically below: