Memory Allocation | getnode | freenode

The getnode() makes use of malloc operation to get a new node from the fornt of availability list, if full it says - overful [ i.e when the malloc return NULL ]
The freenode() makes use of the free operation to add the specified node to the front of availability list



Garbage Collection

Garbage is a block of heap memory that cannot be accessed by the program
  • An allocated block of heap as garbage does not have a reference to it
  • Another kind of memeory error: A reference exists to a block of memeory that is no longer allocated


    • GC Garbage Collection is automatic memory management of dynamically allocated storage. It reclaims unused heap blocks for later use by program.
    GC attempts to reclaim garbage , or memory occupied by objects or pointers that are no longer in use by the program.


    GC are opposite of manual memory management, which requires the programmer to specify which objects to deallocate and return to the memory system.
    Like other memory management techniques, GC may take a significant proportion of total processing time in a program and can thus have significant influence to performance


    Neglects


    Resources other than memeory, such as Network sockets , database handles , user integration, windows and file and device descriptors, are not typically handled by garbage collection.
    Methods used to manage such resources , particularly destructors, may suffice to manage memory as well, leaving no need for a GC system.

    Some GC systems allow such other resources to be associated witha aregion of memory that ,when collected , causes the other resources to be reclaimed , this is called finalization



    Basic Principle

    1. Find data oobjects in a program that cannot be accessed in the future
    2. Reclaim the resources used by those objects


    C,Cpp have garbage collection implementations available by their compilers [ Manually Only ]



    Lists

    The items in the list must be of SAME same data type.

    Operations

    1. createList()
    2. add(index,item)
    3. isEmpty()
    4. size()
    5. remove(index)
    6. traverse()
    7. reverse()
    8. merge()
    9. sort()
    10. search()



    Demonstrating for Singly Linked List

    1. create()
    2. display()
    3. length()
    4. search()
    5. insBegin()
    6. insEnd()
    7. insPos()
    8. insSorted()
    9. delBegin()
    10. delEnd()
    11. delPos()
    12. delItem()

    Code

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

typedef struct Node{
int data;
struct Node *link;
} NODE ;

NODE *head=NULL;

void create(){
// creates a linked list with sinlge node
// without knowing its length
head=(NODE*)malloc(sizeof(NODE));
char ch;
NODE *curptr,*newnode;
curptr=head;
while(1){
printf("Enter the node data: ");
scanf("%d",&curptr->data);
printf("\nThe given data is: %d",curptr->data);
printf("\nDo you want to add one more node?[y/n]: ");
scanf(" %c",&ch);
if(ch=='y'){
newnode=(NODE*)malloc(sizeof(NODE));
curptr->link=newnode;
curptr=newnode;
}
else{
printf("Linked list has been successfully created! ");
curptr->link=NULL;
break;
}
}
}
void display(){
// displays the entire linked list
printf("\nThe elements in the linked list are: ");
NODE *curptr=head;
while(curptr!=NULL){
printf("%d ",curptr->data);
curptr=curptr->link;
}
}
void length(){
// prints the length of the current list
printf("\nThe length of the liked list is: ");
int count=0;
NODE *curptr=head;
while(curptr!=NULL){
curptr=curptr->link;
count++;
}
printf("%d",count);

}
void search(){
// searches a particular item to return its position
printf("\nEnter the element to search: ");
int item;
scanf("%d",&item);
int pos=0;
NODE *curptr=head;
while(curptr->data!=item){
curptr=curptr->link;
pos++;
}
if(curptr->data==item){
printf("\nElement %d found at position %d",item,pos+1);
return;
}
else{
printf("\n Element not found!");
}
}
void insBegin(){
// inserts the given item to the begining of the linked list
NODE *curptr=head;
NODE *newnode=(NODE*)malloc(sizeof(NODE));
printf("\nEnter the element you want to insert at the begining: ");
int item;
scanf("%d",&item);
newnode->data=item;
newnode->link=curptr;
head=newnode;
printf("\n updated list: \n");
display();
}
void insEnd(){
// inserts the given element at the end of the linked list
NODE *curptr=head;
NODE *newnode=(NODE*)malloc(sizeof(NODE));
printf("\nEnter the element you want to insert at the end: ");
int item;
scanf("%d",&item);
newnode->data=item;
while(curptr->link!=NULL){
curptr=curptr->link;
}
curptr->link=newnode;
newnode->link=NULL;
printf("\n Updated list: ");
display();

}
void insPos(){
// inserts the given element at the given position
printf("\n Enter the position to insert the element at: ");
int pos;
scanf("%d",&pos);
if(pos==1){
insBegin();
return;
}
NODE *curptr=head;
NODE *newnode=(NODE*)malloc(sizeof(NODE));
for(int i=0;i<pos-2;i++){
curptr=curptr->link;
}
printf("\nEnter the element you want to insert at the end: ");
int item;
scanf("%d",&item);
newnode->data=item;
newnode->link=curptr->link;
curptr->link=newnode;
printf("\nUpdates list is: ");
display();
return;
}
void insSorted(){
// check this at the end , once everything else works
}
void delBegin(){
// delete an element from the begining of the linked list
NODE *curptr;
curptr=head;// I explicitly did this just to bring it to your notice that a pointer when declared as
// <Datatype> *ptr=var; is same as
// <datatype> *ptr;
// ptr=var;
// since in both places a address vfalue that id of the type <datatype> * in passed and is stored in the
// ptr which is of the type <datatype> *
curptr=curptr->link;
head=curptr;
printf("\nAfter deleting an element from begining \nThe updates list: ");
display();

}
void delEnd(){
// delete an element from the end of the linked list
NODE *curptr=head;
while(curptr->link->link!=NULL){
curptr=curptr->link;
}
curptr->link=NULL;
printf("\nAfter deleting an element from end\nThe updates list: ");
display();
}
void delItem(){
// delete an element from the given position
printf("\nEnter the element to delete: ");
int item;
scanf("%d",&item);
int pos=0;
NODE *curptr=head;
if(curptr->data==item){
delBegin();
return;
}
while(curptr->link->data!=item){
curptr=curptr->link;
pos++;
}
if(curptr->link->data==item){
printf("\nElement %d found at position %d",item,pos+2);
}
else{
printf("\n Element not found!");
return;
}
curptr->link=curptr->link->link;
printf("\nAfter deleting an element from %d\nThe updates list: ",pos+2);
display();

}
void delPos(){
// delete the given item from linked list
printf("\nEnter to position to delete the element from: ");
int pos;
scanf("%d",&pos);
NODE *curptr=head;
if(pos==1){
delBegin();
return;
}
for(int i=0;i<pos-2;i++){
curptr=curptr->link;
}
printf("\nElement at pos %d is: %d\nDeleting it! ",pos,curptr->link->data);
curptr=curptr->link->link;

printf("\nAfter deleting an element from pos %d\nThe updates list: ",pos);
display();

}


int main(){
create();
display();
length();
search();
insBegin();
insEnd();
insPos();
// insSorted();
delBegin();
delEnd();
delPos();
delItem();

return 0;
}



    Code for Circular Linked List

    

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

typedef struct node{
int data;
struct node *link;
} NODE;

NODE *last=NULL;


void display(){
NODE *curptr=last->link;
printf("\nUpdated list: ");
while(curptr!=last){
printf("%d ",curptr->data);
curptr=curptr->link;
}
printf("%d",curptr->data);
return;
}

void create(){
char ch;
int item;
do{
NODE *newnode=(NODE*)malloc(sizeof(NODE));
printf("\nEnter the data: ");
scanf("%d",&newnode->data);
if(last==NULL){
last=newnode;
last->link=newnode;
}else{
newnode->link=last->link;
last->link=newnode;
last=newnode;
}
printf("\nDo you want to continue?[y/n]: ");
scanf(" %c",&ch);
}while(ch=='y');
printf("\nCircular list successfully created: ");
display();
return;
}

int length(){
NODE *curptr=last->link;
int len=1;
while(curptr!=last){
len++;
curptr=curptr->link;
}
return len;
}

void insert(){

void ins_beg(){
NODE *newnode=(NODE*)malloc(sizeof(NODE));
NODE *curptr=last;
printf("\nEnter the element to insert in the begining: ");
// int item;
scanf("%d",&newnode->data);
newnode->link=curptr->link;
curptr->link=newnode;
display();
return;
}


void ins_end(){
NODE *newnode=(NODE*)malloc(sizeof(NODE));
NODE *curptr=last;
printf("\nEnter the element to insert in the end: ");
// int item;
scanf("%d",&newnode->data);
newnode->link=curptr->link;
curptr->link=newnode;
last=newnode;
display();
return;
}
void ins_pos(){
printf("\nEnter the position to insert the element at: ");
int pos;
scanf("%d",&pos);
if(pos==1){
ins_beg();
return;
}
if(pos==length()+1){
ins_end();
return;
}
NODE *curptr=last->link;
for(int i=0;i<pos-2;i++){
curptr=curptr->link;
}
printf("\nEnter the data to insert at %d: ",pos);
NODE *newnode=(NODE*)malloc(sizeof(NODE));
scanf("%d",&newnode->data);
newnode->link=curptr->link;
curptr->link=newnode;
display();

}
ins_beg();
ins_end();
ins_pos();
}

void delete(){

// NODE *curptr=last->link;
void del_beg(){
printf("\nDeleting an element from the begining . . .");
last->link=last->link->link;
display();
}
void del_end(){
printf("\nDeleting an element from the end . . . ");
NODE *curptr=last->link;
while(curptr->link!=last){
curptr=curptr->link;
}
curptr->link=last->link;
last=curptr;
display();
}
void del_pos(){
printf("\nEnter the position to delete an element from: ");
NODE *curptr=last->link;
int pos;
scanf("%d",&pos);
if(pos==1){
del_beg();
return;
}
if(pos==(length())){
del_end();
return;
}
for(int i=0;i<pos-2;i++){
curptr=curptr->link;
}
curptr->link=curptr->link->link;
display();
}
void del_item(){
printf("\nEnter the data to delete: ");
int item;
scanf("%d",&item);
NODE *curptr=last->link;
while(curptr->link->data!=item){
curptr=curptr->link;
}
if(curptr->link==last){
curptr->link=curptr->link->link;
last=curptr;
}
else{
curptr->link=curptr->link->link;
}
display();
return;
}
del_beg();
del_end();
del_pos();
del_item();
return;

}



int main(){
create();
printf("\nThe length is %d",length());
// display();
insert();
delete();
}

    Advantages of Circular Linked list


    1. The circular linked list allows to traver to any node from any node
    2. All the node's address will have valid addresses, instead of NULL pointers
    3. A node can be inserted at or deleted from any position of the linked list
    4. One can start at any node in the list and traverse the whole list



    Double Linked List

    Advantages

    1. The doubly linked list can be traversed in forward or backward directions
    2. if any particular node address is known,one can have both successor node address and predecessor node address that makes insertion and deletion much easier
    3. The doubly linked list is used to represent the trees effectively
    4. This simplified list management.

    Disadvantages

    1. Extra memory is required to store the back pointer
    2. Consider an example shown below

    Code for singly Doubly Linked List

        

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

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

// linked lists are linear ds, linear ds are the ones that follow a **SEQUENCE** , where as
// non linear ds do no need a *SEQUENCE* predefined, they can have their own Sequence defined.

NODE *head=NULL;

void display(){
NODE *curptr=head;
printf("\nUpdated list: ");
while(curptr!=NULL){
printf("%d ",curptr->data);
curptr=curptr->next;
}
return;
}

int length(){
NODE *curptr=head;
int count=0;
while(curptr!=NULL){
curptr=curptr->next;
count++;
}
return count;
}



void insert(){
void ins_beg(){
NODE *curptr=head;
NODE *newnode=(NODE*)malloc(sizeof(NODE));
printf("\nEnter the element you want to insert at the begining: ");
scanf("%d",&newnode->data);
newnode->prev=NULL;
newnode->next=curptr;
curptr->prev=newnode;
curptr=newnode;
head=curptr;
display();
}
void ins_end(){
NODE *curptr=head;
NODE *newnode=(NODE*)malloc(sizeof(NODE));
printf("\nEnter the element you want to insert at the end: ");
scanf("%d",&newnode->data);
while(curptr->next!=NULL){
curptr=curptr->next;
}
curptr->next=newnode;
newnode->prev=curptr;
newnode->next=NULL;
display();
}
void ins_pos(){
NODE *curptr=head;
printf("\nEnter the position you want to insert element at: ");
int pos;
scanf("%d",&pos);
if(pos==1){
ins_beg();
return;
}
if(pos==length()+1){
ins_end();
return;
}
for(int i=0;i<pos-1;i++){
curptr=curptr->next;
}
printf("\nEnter the element you want to insert: ");
NODE *newnode=(NODE*)malloc(sizeof(NODE));
scanf("%d",&newnode->data);
newnode->next=curptr;
newnode->prev=curptr->prev;
curptr->prev->next=newnode;
curptr->prev=newnode;
display();
}
ins_beg();
ins_end();
ins_pos();
return ;
}

void delete(){
void del_beg(){
NODE *curptr=head;
printf("\nDeleting an element from the begining . . .");
head=curptr->next;
display();
return;
}
void del_end(){
NODE *curptr=head;
printf("\nDeleting an element from the ending. . .");
while(curptr->next!=NULL){
curptr=curptr->next;
}
curptr->prev->next=NULL;
display();
return;
}
void del_pos(){
NODE *curptr=head;
printf("\nEnter the position to delete the element from : ");
int pos;
scanf("%d",&pos);
if(pos==1){
del_beg();
return;
}
if(pos==length()){
printf("test");
del_end();
return;
}
for(int i=0;i<pos-1;i++){
curptr=curptr->next;
}
curptr->prev->next=curptr->next;
display();
}
del_beg();
del_end();
del_pos();
return;
}

void create(){
NODE *curptr=head;
char ch;

do {
NODE *newnode=(NODE*)malloc(sizeof(NODE));
printf("\nEnter the data you want to add: ");
scanf("%d",&newnode->data);
if(head==NULL){
newnode->prev=NULL;
newnode->next=NULL;
curptr=newnode;
head=curptr;
}
else{
curptr->next=newnode;
newnode->prev=curptr;
newnode->next=NULL;
curptr=newnode;
}
printf("\nDo you want to add more?[y/n]: ");
scanf(" %c",&ch);
} while (ch=='y');
printf("\nDoubly linked list successfully created! ");
display();
}

int main(){
create();
insert();
delete();
}

    Summary

    1. In stacks and queues, the alloation of items is done by means of sequential allocation technique using arrays where as in linked lists it is done by dynamic memory allocation technique.

    2. Advantages of Linked Lists OVER arrays

      1. Efficient memory utilisation
      2. Insertion and deletion are easier and efficient
      3. Extensive manipulations
      4. Arbitrary memory locations
    3. External Pointer
      The very first node in the linked list
      Availability List
      AKA free list is the term used by the memory manager like malloc and calloc to use the space that is un-allocated at the moment. This space in the the chunks of blocks
    4. Header Linked List
      is a linked list which always has info contains a special node called as the header node at the begining of the list.
      The info field of such a header node generally contains the global informatoin of the entire list.

      Types of header Linked Lists

      1. Grounded Header Linked Lists
        The grounded header linked list is also referred as singly header linked list. In this the last node's link field contains the NULL pointer.
      2. Circular Header Linked Lists
        like other circular linked lists, the last node's link field points back the header node

    5. Applications of Linked Lists

      1. Addition of two polynomials
      2. Addition of two long positive integers

    6. Types of Linked Lists [bonus]

      1. Single
      2. Double
      3. Circular Singly
      4. Circular Doubly
      5. Header
        1. Grounded
        2. Circular
      6. Multilevel / Nested [ a linked list in a linked list]
        

struct Node {
int data;
struct Node *next;
struct Node *child; // pointer to another list
};
    Stack