Embedded Systems Learning Academy - User contributions [en]

Interview Preparation Linked List

2017-04-01T01:52:54Z

Arvindallawadi: /* Removing duplicate elements */

A linked list is like an array that can grow without restriction of a fixed-size array. The disadvantage is that unlike an array that we can access by an index, we have to iterate through the elements of the list. This is because unlike an array which has contiguous memory, linked list memory is usually scattered.

To show a picture, an array looks like this :
<code>[0] [1] [2] [3] ...</code>

A linked list looks like this :
<code>head --> [0] --> [1] --> [2] --> [3] --> [NULL]</code>

Each element of the linked list can be scattered in memory and a pointer is used to indicate where in memory you can find the next element. If the next element doesn't exist, a NULL pointer is used to mark the end.

== Singly Linked List==

=== Structure ===
<syntaxhighlight lang="c">
typedef struct linked_list_node {
struct linked_list_node *next;
int data;
} linked_list_t;
</syntaxhighlight>

 
Observations :
* '''<code>linked_list_t</code>''' is used such that when we want to declare the linked-list node, we can just use '''<code>linked_list_t node</code>''' rather than '''<code>struct linked_list_node node;</code>'''
*: For the '''<code>*next;</code>''' linked-list pointer, we have to explicitly use a '''<code>struct</code>''' keyword because at that point in time, the '''<code>linked_list_t</code>''' has not been declared.
* The '''<code>int data;</code>''' is the actual data of a node, which could be '''<code>void*</code>''' too.

 
=== Allocation and Adding elements ===
<syntaxhighlight lang="c">
#include <stdlib.h> /* malloc() */

/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */
static linked_list_t *g_head = NULL;

void ll_allocate_head(int n)
{
g_head = malloc(sizeof(*g_head));
g_head->data = n;
g_head->next = NULL;
}

void ll_add_to_beg(int n)
{
if (NULL == g_head) {
ll_allocate_head(n);
}
else {
linked_list_t *new_elm = malloc(sizeof(linked_list_t));

/* Copy the data, and set this node's next to the older head */
new_elm->next = g_head;
new_elm->data = n;

/* Head becomes this element since we wanted to add to beginning */
g_head = new_elm;
}
}

void ll_add_to_end(int n)
{
if (NULL == g_head) {
ll_allocate_head(n);
}
else {
/* Need to get to the tail first */
linked_list_t *tail = g_head;
while(tail->next != NULL) {
tail = tail->next;
}

linked_list_t *new_elm = malloc(sizeof(linked_list_t));
new_elm->next = NULL;
new_elm->data = n;

/* Simply add new element to the tail */
tail->next = new_elm;
}
}
</syntaxhighlight>

 

=== List Reversal ===
<syntaxhighlight lang="c">

#include <stdlib.h> /* malloc() */

/*Function to reverse a singly linked list by iterating through the list*/
void ll_reverse(linked_list_t** data)
{
linked_list_t* prev = NULL; /*previous node is made NULL*/
linked_list_t* g_head= *data; /*data is assigned to head node*/
linked_list_t* next;
while (g_head)
{
next = g_head->next;
g_head->next = prev;
prev = g_head;
g_head= next;
}
*data= prev;
}
</syntaxhighlight>
 

 

=== Loop in the List===
<syntaxhighlight lang="c">
#include <stdlib.h> /* malloc() */

/*Function to reverse a singly linked list by iterating through the list*/
bool ll_loop(linked_list_t* head)
{
linked_list_t *slow= head, *fast = head;

while((slow!=NULL)&&(fast->next!=NULL)&&(fast!=NULL))//checking to see if the current position or the
{ //successive position is pointing to a NULL.
slow = slow-> next; //slow pointer
fast = fast->next->next; //fast pointer
if(slow==fast){ //comparing to see if the slow and fast pointers meet at a node.
return TRUE; //return true if the loop exists
}
}
return FALSE; //return false if the loop doesnt exists.
}

</syntaxhighlight>

 

=== Removing duplicate elements ===
<syntaxhighlight lang="c">
#include <stdlib.h> /* malloc() */

/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */
static linked_list_t *g_head = NULL;

void remove_dups(linked_list_t* head){ //we are never deleting the head node

linked_list_t* current = head; //current node
linked_list_t *pointer1, *duplicate;

while(current->next != NULL){//traversing the list pointed by current
pointer1 = current;// the current node is copied into pointer1
while(pointer1->next != NULL){// traversing the list pointed by pointer1
if(pointer1->next->data == current->data){ //Checking for duplicates by comparing the current data and pointer1 data of next node
duplicate = pointer1->next;// copy the address of pointer1 node (which contains duplicate data) into duplicate
pointer1->next = pointer1->next->next;//placing the new address i.e. the next node address into pointer to which it will be pointing next
free(duplicate);//free the duplicate node (which contains duplicate data)
}
pointer1 = pointer1->next;//move to the next node
}
current = current->next;//current pointing to next node

}
}

}
</syntaxhighlight>

 

=== Palindrome ===
<syntaxhighlight lang="c">
#include <stdlib.h> /* malloc() */

/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */
static linked_list_t *g_head = NULL;

bool isPalindrome(linked_list_t *head){
linked_list_t *reverse = reverse(head);// calling function to reverse the list
return checkPalindrome(head,reverse);// calling function to check if the list is Palindrome
}

linked_list_t* reverse(linked_list_t *head1){
linked_list_t *temp = NULL;

while(head1->next != NULL){
linked_list_t *new_reverse_node = (linked_list_t*)malloc(sizeof(linked_list_t));// new node create to copy the current list in reverse order
new_reverse_node->data = head1->data;// copy head data into new node
new_reverse_node->next = temp;//reversing the list by making the first node the last node
temp = new_reverse_node;
head1 = head1->next;//traverse till the end of the list
}
return temp;
}

bool checkPalindrome(linked_list_t *list1, linked_list_t *list2){
while(list1->next != NULL && list2->next != NULL){
if(list1->data != list2->data){
return false;
}
list1 = list1->next;
list2 = list2->next;
}
if(list1->next == NULL && list2->next == NULL){
return true;
}
}
</syntaxhighlight>

 

== Doubly Linked List ==
Let's elaborate on our linked list such that we have the '''next''' and the '''previous''' links. We will have the added benefit of going backwards from an element at the cost of the memory requirement of an extra pointer along with more code to deal with this extra pointer.
<syntaxhighlight lang="c">
typedef struct linked_list_node {
struct linked_list_node *next; /*next node*/
struct linked_list_node* prev; /*previous node*/
int data;
} linked_list_t;

/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */

static linked_list_t *g_head = NULL;

/*new node is created and a pointer is returned */

linked_list_t *create_new_node(int n ) {
linked_list_t *new_node
= malloc(sizeof(linked_list_t)); /*creating a new node*/
new_node->data = n; /*assigning input to data*/
new_node->prev = NULL; /*previous and next links are initialized to NULL*/
new_node->next = NULL;
return new_node; /*returning a pointer*/
}

/*Inserting node at head */
void insert_at_head(int n) {
linked_list_t* new_node = create_new_node(n); /*creating a new node*/

if(g_head == NULL) { /*condition to check if the head node is empty*/
g_head = new_node;
return;
}

g_head->prev = new_node; /*assigning new node to head node */
new_node->next = g_head;
g_head = new_node;
}

/*to insert a node at tail*/
void insert_at_tail(int n) {
linked_list_t* temp = g_head;
linked_list_t* new_node = create_new_node(n); //creating a new node

if(g_head == NULL) {
g_head = new_node;
return;
}

while(temp->next != NULL) temp = temp->next; //last node
temp->next = new_node;
new_node->prev = temp;
}

</syntaxhighlight>
 

== Delete a node in a linked list==
<syntaxhighlight lang="c">
typedef struct linked_list_node {
struct linked_list_node *next; /*next node*/
int data;
} linked_list_t;

void delete_node(linked_list_t *g_head, linked_list_t *N)
{
/* to delete head node */
if(g_head == N)
{
if(g_head->next == NULL)
{
return;
}

/* Copy next node data to head node */
g_head->data = g_head->next->data;

/* copy address of next node to N*/
N = g_head->next;

/* delete next node */
g_head->next = g_head->next->next;

free(N);
return;
}

/* to delete a node other than the first(head) node */
/*previous node */
linked_list_t *prev = g_head;
while(prev->next != NULL && prev->next != N)
prev = prev->next;

/*check if prev node exists */
if(prev->next == NULL)
{
return;
}

/*Delete that node from Linked List
prev->next = prev->next->next;

free(N);

return;
}
</syntaxhighlight>
 

== Make List unique using STL and recursion ==
The task - given a list of '''''n''''' integers in a list, remove all the duplicate values so that what remains is a list of unique values.
 
This example exclusively makes use of STL Library '''''<list>''''' and '''''recursion'''''.
 
'''''Approach:''''' First define function '''''member_of''''' that checks if a value '''''x'''''' is present in the list.
<syntaxhighlight lang="c">
bool member_of(const int value, const list<int>& my_list, list<int>::const_iterator it)
{
if (it == my_list.end())
return false;
return (*it == value) || member_of(value, my_list, ++it);
}
</syntaxhighlight>
 
Now, take out the first value. Make the rest of the list unique. Then if the value we took out is not in the rest of the list, put it back. Otherwise, leave it out.
 
<syntaxhighlight lang="c">
void isListUnique(list<int>& alist)
{
if (alist.size() <= 1) return; // base case

int first = alist.front();
alist.erase(alist.begin()); // remove the first element

isListUnique(alist); // make the rest of the list unique

if (!member_of(first, alist, alist.begin()))
{
alist.push_front(first); // put back the first element
}
}
</syntaxhighlight>
 
== Reverse a linked list using STL and recursion ==
'''''Task -''''' Reverse the values of a list of '''''n''''' integers.
 
This example exclusively using STL library '''''<list>''''' and '''''recursion'''''.
 
'''''Approach:'''''
 
'''''Step 1:''''' Take out the first value of the list.
 
'''''Step 2:''''' Reverse the rest of the list recursively.
 
'''''Step 3:''''' Append the removed value to the end of the reversed rest of the list.
<syntaxhighlight lang="c">
void listReverse(list<int>& my_list)
{
if (my_list.size() <= 1) return; // base case

int first = my_list.front();
my_list.erase(my_list.begin()); // remove the first element

listReverse(my_list); // reverse the rest of the list
my_list.push_back(first); // append the first element at the end
}
</syntaxhighlight>

Interview Preparation Linked List

2017-04-01T01:50:09Z

Arvindallawadi: /* Removing duplicate elements */

A linked list is like an array that can grow without restriction of a fixed-size array. The disadvantage is that unlike an array that we can access by an index, we have to iterate through the elements of the list. This is because unlike an array which has contiguous memory, linked list memory is usually scattered.

To show a picture, an array looks like this :
<code>[0] [1] [2] [3] ...</code>

A linked list looks like this :
<code>head --> [0] --> [1] --> [2] --> [3] --> [NULL]</code>

Each element of the linked list can be scattered in memory and a pointer is used to indicate where in memory you can find the next element. If the next element doesn't exist, a NULL pointer is used to mark the end.

== Singly Linked List==

=== Structure ===
<syntaxhighlight lang="c">
typedef struct linked_list_node {
struct linked_list_node *next;
int data;
} linked_list_t;
</syntaxhighlight>

 
Observations :
* '''<code>linked_list_t</code>''' is used such that when we want to declare the linked-list node, we can just use '''<code>linked_list_t node</code>''' rather than '''<code>struct linked_list_node node;</code>'''
*: For the '''<code>*next;</code>''' linked-list pointer, we have to explicitly use a '''<code>struct</code>''' keyword because at that point in time, the '''<code>linked_list_t</code>''' has not been declared.
* The '''<code>int data;</code>''' is the actual data of a node, which could be '''<code>void*</code>''' too.

 
=== Allocation and Adding elements ===
<syntaxhighlight lang="c">
#include <stdlib.h> /* malloc() */

/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */
static linked_list_t *g_head = NULL;

void ll_allocate_head(int n)
{
g_head = malloc(sizeof(*g_head));
g_head->data = n;
g_head->next = NULL;
}

void ll_add_to_beg(int n)
{
if (NULL == g_head) {
ll_allocate_head(n);
}
else {
linked_list_t *new_elm = malloc(sizeof(linked_list_t));

/* Copy the data, and set this node's next to the older head */
new_elm->next = g_head;
new_elm->data = n;

/* Head becomes this element since we wanted to add to beginning */
g_head = new_elm;
}
}

void ll_add_to_end(int n)
{
if (NULL == g_head) {
ll_allocate_head(n);
}
else {
/* Need to get to the tail first */
linked_list_t *tail = g_head;
while(tail->next != NULL) {
tail = tail->next;
}

linked_list_t *new_elm = malloc(sizeof(linked_list_t));
new_elm->next = NULL;
new_elm->data = n;

/* Simply add new element to the tail */
tail->next = new_elm;
}
}
</syntaxhighlight>

 

=== List Reversal ===
<syntaxhighlight lang="c">

#include <stdlib.h> /* malloc() */

/*Function to reverse a singly linked list by iterating through the list*/
void ll_reverse(linked_list_t** data)
{
linked_list_t* prev = NULL; /*previous node is made NULL*/
linked_list_t* g_head= *data; /*data is assigned to head node*/
linked_list_t* next;
while (g_head)
{
next = g_head->next;
g_head->next = prev;
prev = g_head;
g_head= next;
}
*data= prev;
}
</syntaxhighlight>
 

 

=== Loop in the List===
<syntaxhighlight lang="c">
#include <stdlib.h> /* malloc() */

/*Function to reverse a singly linked list by iterating through the list*/
bool ll_loop(linked_list_t* head)
{
linked_list_t *slow= head, *fast = head;

while((slow!=NULL)&&(fast->next!=NULL)&&(fast!=NULL))//checking to see if the current position or the
{ //successive position is pointing to a NULL.
slow = slow-> next; //slow pointer
fast = fast->next->next; //fast pointer
if(slow==fast){ //comparing to see if the slow and fast pointers meet at a node.
return TRUE; //return true if the loop exists
}
}
return FALSE; //return false if the loop doesnt exists.
}

</syntaxhighlight>

 

=== Removing duplicate elements ===
<syntaxhighlight lang="c">
#include <stdlib.h> /* malloc() */

/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */
static linked_list_t *g_head = NULL;

void remove_dups(linked_list_t* g_head){ //we are never deleting the head node

linked_list_t* current = g_head; //current node
linked_list_t *pointer1, *duplicate;

while(current->next != NULL){//traversing the list pointed by current
pointer1 = current;// the current node is copied into pointer1
while(pointer1->next != NULL){// traversing the list pointed by pointer1
if(pointer1->next->data == current->data){ //Checking for duplicates by comparing the current data and pointer1 data of next node
duplicate = pointer1->next;// copy the address of pointer1 node (which contains duplicate data) into duplicate
pointer1->next = pointer1->next->next;//placing the new address i.e. the next node address into pointer to which it will be pointing next
free(duplicate);//free the duplicate node (which contains duplicate data)
}
pointer1 = pointer1->next;//move to the next node
}
current = current->next;//current pointing to next node

}
}

}
</syntaxhighlight>

 

=== Palindrome ===
<syntaxhighlight lang="c">
#include <stdlib.h> /* malloc() */

/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */
static linked_list_t *g_head = NULL;

bool isPalindrome(linked_list_t *head){
linked_list_t *reverse = reverse(head);// calling function to reverse the list
return checkPalindrome(head,reverse);// calling function to check if the list is Palindrome
}

linked_list_t* reverse(linked_list_t *head1){
linked_list_t *temp = NULL;

while(head1->next != NULL){
linked_list_t *new_reverse_node = (linked_list_t*)malloc(sizeof(linked_list_t));// new node create to copy the current list in reverse order
new_reverse_node->data = head1->data;// copy head data into new node
new_reverse_node->next = temp;//reversing the list by making the first node the last node
temp = new_reverse_node;
head1 = head1->next;//traverse till the end of the list
}
return temp;
}

bool checkPalindrome(linked_list_t *list1, linked_list_t *list2){
while(list1->next != NULL && list2->next != NULL){
if(list1->data != list2->data){
return false;
}
list1 = list1->next;
list2 = list2->next;
}
if(list1->next == NULL && list2->next == NULL){
return true;
}
}
</syntaxhighlight>

 

== Doubly Linked List ==
Let's elaborate on our linked list such that we have the '''next''' and the '''previous''' links. We will have the added benefit of going backwards from an element at the cost of the memory requirement of an extra pointer along with more code to deal with this extra pointer.
<syntaxhighlight lang="c">
typedef struct linked_list_node {
struct linked_list_node *next; /*next node*/
struct linked_list_node* prev; /*previous node*/
int data;
} linked_list_t;

/* Assume this is a source file, such as linked_list.c */
/* g for "global" variable of this file, and static for "private variable" of this file */

static linked_list_t *g_head = NULL;

/*new node is created and a pointer is returned */

linked_list_t *create_new_node(int n ) {
linked_list_t *new_node
= malloc(sizeof(linked_list_t)); /*creating a new node*/
new_node->data = n; /*assigning input to data*/
new_node->prev = NULL; /*previous and next links are initialized to NULL*/
new_node->next = NULL;
return new_node; /*returning a pointer*/
}

/*Inserting node at head */
void insert_at_head(int n) {
linked_list_t* new_node = create_new_node(n); /*creating a new node*/

if(g_head == NULL) { /*condition to check if the head node is empty*/
g_head = new_node;
return;
}

g_head->prev = new_node; /*assigning new node to head node */
new_node->next = g_head;
g_head = new_node;
}

/*to insert a node at tail*/
void insert_at_tail(int n) {
linked_list_t* temp = g_head;
linked_list_t* new_node = create_new_node(n); //creating a new node

if(g_head == NULL) {
g_head = new_node;
return;
}

while(temp->next != NULL) temp = temp->next; //last node
temp->next = new_node;
new_node->prev = temp;
}

</syntaxhighlight>
 

== Delete a node in a linked list==
<syntaxhighlight lang="c">
typedef struct linked_list_node {
struct linked_list_node *next; /*next node*/
int data;
} linked_list_t;

void delete_node(linked_list_t *g_head, linked_list_t *N)
{
/* to delete head node */
if(g_head == N)
{
if(g_head->next == NULL)
{
return;
}

/* Copy next node data to head node */
g_head->data = g_head->next->data;

/* copy address of next node to N*/
N = g_head->next;

/* delete next node */
g_head->next = g_head->next->next;

free(N);
return;
}

/* to delete a node other than the first(head) node */
/*previous node */
linked_list_t *prev = g_head;
while(prev->next != NULL && prev->next != N)
prev = prev->next;

/*check if prev node exists */
if(prev->next == NULL)
{
return;
}

/*Delete that node from Linked List
prev->next = prev->next->next;

free(N);

return;
}
</syntaxhighlight>
 

== Make List unique using STL and recursion ==
The task - given a list of '''''n''''' integers in a list, remove all the duplicate values so that what remains is a list of unique values.
 
This example exclusively makes use of STL Library '''''<list>''''' and '''''recursion'''''.
 
'''''Approach:''''' First define function '''''member_of''''' that checks if a value '''''x'''''' is present in the list.
<syntaxhighlight lang="c">
bool member_of(const int value, const list<int>& my_list, list<int>::const_iterator it)
{
if (it == my_list.end())
return false;
return (*it == value) || member_of(value, my_list, ++it);
}
</syntaxhighlight>
 
Now, take out the first value. Make the rest of the list unique. Then if the value we took out is not in the rest of the list, put it back. Otherwise, leave it out.
 
<syntaxhighlight lang="c">
void isListUnique(list<int>& alist)
{
if (alist.size() <= 1) return; // base case

int first = alist.front();
alist.erase(alist.begin()); // remove the first element

isListUnique(alist); // make the rest of the list unique

if (!member_of(first, alist, alist.begin()))
{
alist.push_front(first); // put back the first element
}
}
</syntaxhighlight>
 
== Reverse a linked list using STL and recursion ==
'''''Task -''''' Reverse the values of a list of '''''n''''' integers.
 
This example exclusively using STL library '''''<list>''''' and '''''recursion'''''.
 
'''''Approach:'''''
 
'''''Step 1:''''' Take out the first value of the list.
 
'''''Step 2:''''' Reverse the rest of the list recursively.
 
'''''Step 3:''''' Append the removed value to the end of the reversed rest of the list.
<syntaxhighlight lang="c">
void listReverse(list<int>& my_list)
{
if (my_list.size() <= 1) return; // base case

int first = my_list.front();
my_list.erase(my_list.begin()); // remove the first element

listReverse(my_list); // reverse the rest of the list
my_list.push_back(first); // append the first element at the end
}
</syntaxhighlight>