Linked Lists (Single, Doubly, Circularly, Self Adjusting)

circularlyLinkedList.c

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

typedef struct _node{
    int data;
    struct _node *next;
} node;

typedef node circularlyLinkedList;


void Init(circularlyLinkedList * L){
L->next = L;
}

void printList(circularlyLinkedList * start){

node * pointer;

pointer = start->next;

while(pointer->next!=start){
      printf("%d ",pointer->data);
      pointer = pointer->next;
}
printf("%d \n",pointer->data);

}

void Delete(int X, circularlyLinkedList * start){

node * pointer, * temp;
pointer = start;

while(pointer->next!=start && pointer->next->data!=X)
pointer = pointer->next;

if(pointer->next!=NULL){
temp = pointer->next;
pointer->next  = temp->next;
free(temp);
}
printList(start);

}

void Insert(int X, circularlyLinkedList * start){

node *pointer,*temp;

pointer = start;

while(pointer->next!=start)
      pointer = pointer->next;

temp = (node *)malloc(sizeof(node));
temp->data = X;
temp->next = start;
pointer->next = temp;

printList(start);
}

int main(){

int i;
circularlyLinkedList L;

Init(&L);

for(i=1;i<10;i++)
    Insert(i,&L);

Delete(9,&L);
Delete(1,&L);

return 0;
}

doublyLinkedList.c

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

typedef struct _node{
    int data;
    struct _node *next;
    struct _node *prev;
} node;

typedef node doublyLinkedList;

//We will use a sentinel node
void Init(doublyLinkedList * L){
L->next=NULL;
L->prev=NULL;
}

void printList(doublyLinkedList * L){

node * P;
P=L->next;

while(P!=NULL){
printf("%d ",P->data);
P=P->next;
}
printf("\n");
}

void Delete(int X, doublyLinkedList * L){

node * P;
node * temp;
P = L;

while(P!=NULL && P->data!=X)
P = P->next;

temp = P->prev;
temp->next = P->next;
if(P->next!=NULL)
(P->next)->prev = temp;
free(P);

printList(L);

}

//We will insert in the front.
void Insert(int X, doublyLinkedList * L){

node * temp, * Q;
temp = (node *)malloc(sizeof(node));
if(temp!=NULL){
temp->data = X;
Q = L->next;

L->next = temp;
temp->prev = L;

temp->next = Q;
if(Q!=NULL)
Q->prev = temp;
}

printList(L);
}

void InsertInEND(int X, doublyLinkedList * L){

node * temp, *Q;

Q = L;

temp = (node *)malloc(sizeof(node));
temp->data = X;
temp->next = NULL;
temp->prev = NULL;

while(Q->next!=NULL){
Q = Q->next;
}

Q->next=temp;
temp->prev=Q;

printList(L);
}

int main(){

doublyLinkedList L;
int i;

Init(&L);

for(i=1; i < 10; i++)
    InsertInEND(i, &L);

for(i=10; i < 20; i++)
    Insert(i, &L);

for(i=1; i < 10; i += 2)
    Delete(i,&L);
}

selfAdjustingLinkedList.c

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

typedef struct _node{
    int data;
    struct _node *next;
} node;

typedef node SelfAdjustingLinkedList;

void Init(SelfAdjustingLinkedList * L){
L->next = NULL;
}

void printList(SelfAdjustingLinkedList * L){

node * pointer;

pointer = L->next;

while(pointer!=NULL){
     printf("%d ",pointer->data);
     pointer = pointer->next;
}
printf("\n");
}

void Insert(int X, SelfAdjustingLinkedList * L){

node * temp;

temp = (node *)malloc(sizeof(node));
temp->data = X;
temp->next = L->next;
L->next = temp;

printList(L);
}


node * Find(int X, SelfAdjustingLinkedList * L){

node * pointer = NULL, * prevpointer = NULL;
prevpointer = L;
pointer = L->next;

while(pointer!=NULL && pointer->data !=X){
      prevpointer = pointer;
      pointer = pointer->next;
}

if(prevpointer != L){
prevpointer->next = pointer->next;
pointer->next = L->next;
L->next = pointer;
}

printList(L);
return pointer;

}

int main(){

SelfAdjustingLinkedList L;
node * someNode;
int i;

Init(&L);

for(i=1;i<10;i++)
    Insert(i,&L);

Find(5,&L);
Find(1,&L);
Find(5,&L);
Find(9,&L);
Find(9,&L);
return 0;

}

singlyLinkedList.c

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

typedef struct _node{
    int data;
    struct _node *next;
} node;

typedef node linearLinkedList;

//We will use a sentinel node
void Init(linearLinkedList * L){
L->next=NULL;
}

void printList(linearLinkedList * L){

node * P;
P=L->next;

while(P!=NULL){
printf("%d ",P->data);
P=P->next;
}
printf("\n");
}

void Delete(int X, linearLinkedList * L){

node * P;
node * temp;
P = L;

while(P->next!=NULL && P->next->data!=X)
P = P->next;

if(P->next!=NULL){
temp = P->next;
P->next  = temp->next;
free(temp);
}
printList(L);

}

//We will insert in the front.
void Insert(int X, linearLinkedList * L){

node * temp;
temp = (node *)malloc(sizeof(node));
if(temp!=NULL){
temp->data = X;
temp->next = L->next;
L->next = temp;
}
printList(L);
}

node * Find(int X, linearLinkedList * L){

node * pointer = NULL, * prevpointer = NULL;
prevpointer = L;
pointer = L->next;

while(pointer!=NULL && pointer->data !=X){
      prevpointer = pointer;
      pointer = pointer->next;
}

if(prevpointer != L){
prevpointer->next = pointer->next;
pointer->next = L->next;
L->next = pointer;
}

printList(L);
return pointer;

}

int main(){

linearLinkedList L;
int i;

Init(&L);

for(i=1; i < 10; i++)
    Insert(i, &L);

Find(5,&L);
Find(1,&L);
Find(5,&L);
Find(9,&L);
Find(9,&L);
return 0;
}

The topics are discussed at http://slashn.wordpress.com/category/linear-data-structures/