Difference between revisions of "Interview Preparation Linked List"
Proj user12 (talk | contribs) (→Singly Linked List) |
Proj user10 (talk | contribs) (→Allocation and Adding elements) |
||
| Line 84: | Line 84: | ||
<BR/> | <BR/> | ||
| + | |||
=== List Reversal === | === List Reversal === | ||
<syntaxhighlight lang="c"> | <syntaxhighlight lang="c"> | ||
Revision as of 20:58, 1 December 2016
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 :
[0] [1] [2] [3] ...
A linked list looks like this :
head --> [0] --> [1] --> [2] --> [3] --> [NULL]
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.
Contents
Singly Linked List
Structure
typedef struct linked_list_node {
struct linked_list_node *next;
int data;
} linked_list_t;
Observations :
-
linked_list_tis used such that when we want to declare the linked-list node, we can just uselinked_list_t noderather thanstruct linked_list_node node;- For the
*next;linked-list pointer, we have to explicitly use astructkeyword because at that point in time, thelinked_list_thas not been declared.
- For the
- The
int data;is the actual data of a node, which could bevoid*too.
Allocation and Adding elements
#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;
}
}
List Reversal
#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;
linked_list_t* g_head= *data;
linked_list_t* next;
while (g_head)
{
next = g_head->next;
g_head->next = prev;
prev = g_head;
g_head= next;
}
*data= prev;
}
Loop in the List
#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.
}
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.
TODO
