Linked List & Memory Management PDF Notes

 LINKED LIST & MEMORY MANAGEMENT MODULE III Jacob P Cherian Asst.Professor Dept.of CSE, Saintgits College of Engineering...

 LINKED LIST & MEMORY MANAGEMENT MODULE III Jacob P Cherian Asst.Professor Dept.of CSE, Saintgits College of Engineering 1 Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  CONTENTS Self Referential Structures Dynamic Memory Allocation Singly Linked List Operations on Linked List Doubly Linked List Circular Linked List Stacks and Queues using Linked List Polynomial representation using Linked List Memory allocation and deallocation First-fit, Best-fit and Worst-fit allocation schemes 2 Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Self Referential Structures Self-referential structures are those which have structure pointer(s) of the same type as their member(s). struct student { char name; int roll; char dept; int marks; struct student *next; }; Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Self Referential Structures- Memory Visualization name roll dept marks next 2000 2004 2008 2012 2016 2020 2024 2028 2032 name roll dept marks next 7500 7504 7508 7512 7516 7520 7524 7528 7532 Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Linked List- Quick Overview DATA POINTER TO NEXT NODE 5 Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Types of Linked Lists Singly Linked Lists Doubly Linked Lists Circular Linked Lists Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  SINGLY LINKED LIST Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Singly Linked List Each element in a linked list is called a node. A single node contains data and a pointer to the next node which helps in maintaining the structure of the list. A singly linked list allows traversal only in a single direction 9 Data Part Pointer to Next Node Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Singly Linked List The first node is called the head; it points to the first node of the list and helps us access every other element in the list. The last node, also sometimes called the tail, points to NULL which helps us in determining when the list ends. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Visual Representation head 9 4 2 1 5 8 -1 0 tail 6 16 3 7 NUL L Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Representation of Linked 12 9 List in Memory 7 7 2016 12 4020 2000 2004 2008 2012 2016 2020 2024 2028... MAIN MEMORY 9 NULL... 4004 4008 4012 4016 4020 4024 4028 4032 Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Common Linked List Operations Search for a node in the List Add a node to the List Remove a node from the List Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Insertion at the Beginning Create a new node with given data. Point new node’s next to old head. Point head to this new node. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Insertion at the Beginning head 8 -1 0 tail 2 16 3 7 NUL L Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Insertion at the Beginning Insert a New Node 5 At the beginning head 8 -1 0 tail 2 16 3 7 NUL L Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Insertion at the Beginning head 5 8 -1 0 tail 2 16 3 7 NUL L Create a new node with given data. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Insertion at the Beginning head 5 8 -1 0 tail 2 16 3 7 NUL L Point new node’s next to old head. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Insertion at the Beginning head 5 8 -1 0 tail 2 16 3 7 NUL L Point head to the new node. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 NULL 5000 5004 5008 5012 5016... 6024 6028... Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 NULL 5 5000 5004 5008 5012 5016... 6024 6028... Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 NULL 5 2000 5000 5004 5008 5012 5016... 6024 6028... Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Insertion at Middle/End or Insertion after Node X Create a new node with given data. Point new node’s next to old X’s next. Point X’s next to the new node Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Insertion at the End head 5 8 -1 0 tail 2 16 3 7 NUL L Insert a New Node 9 At the End Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Insertion at the End head 5 8 -1 0 tail 2 16 3 7 NUL 9 L Create a new node with given data. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Insertion at the End head 5 8 -1 0 tail 2 16 3 7 9 NUL L Point new node’s next to old X’s next. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Insertion at the End head 5 8 -1 0 tail 2 16 3 7 9 NUL L Point X’s next to the new node Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 NULL 5 2000 5000 5004 5008 5012 5016... 6024 6028... Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 800 5 2000 9 0 5000 5004 5008 5012 Downloaded Jacob P Cherian, Assistant 5016... CSE, Saintgits 6024 College fromofKtunotes.in Professor, Department 6028... of Engineering 8000 8004 Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 800 5 2000 9 NUL 0 L 5000 5004 5008 5012 Downloaded Jacob P Cherian, Assistant 5016... CSE, Saintgits 6024 College fromofKtunotes.in Professor, Department 6028... of Engineering 8000 8004  Basic Operations: Insertion after Position X head X 5 8 -1 0 tail 2 16 3 7 NUL L Insert a New Node 9 After position 3 Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Insertion after Position X 9 head X 5 8 -1 0 tail 2 16 3 7 NUL L Create a new node with given data. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Insertion after Position X 9 head X 5 8 -1 0 tail 2 16 3 7 NUL L Point new node’s next to old X’s next. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Insertion at a particular position 9 head X 5 8 -1 0 tail 2 16 3 7 NUL L Point X’s next to the new node Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 NULL 5 2000 5000 5004 5008 5012 5016... 6024 6028... Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Memory Visualization 8 3016 -1 8000 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 800 5 2000 9 400 0 4 5000 5004 5008 5012 Downloaded Jacob P Cherian, Assistant 5016... CSE, Saintgits 6024 College fromofKtunotes.in Professor, Department 6028... of Engineering 8000 8004  Basic Operations: Deletion at the Beginning Get the node pointed by head as temp Point head to temp’s next Free the memory used by node temp Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Deletion at the Beginning head 5 8 -1 0 tail 2 16 3 7 NUL L Delete the node from the beginning Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Deletion at the Beginning temp head 5 8 -1 0 tail 2 16 3 7 NUL L Get the node pointed by head as temp Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Deletion at the Beginning temp head 5 8 -1 0 tail 2 16 3 7 NUL L Point head to temp’s next Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Deletion at the Beginning head 8 -1 0 tail 2 16 3 7 NUL L Free the memory used by node temp Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 NULL 5 2000 5000 5004 5008 5012 5016... 6024 6028... Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Freed Memory ( Can be re-allocated) Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 NULL 5 2000 5000 5004 5008 5012 5016... 6024 6028... Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Deletion at Middle/End or Deletion after Node X Get the node pointed by X as temp Point X’s next to temp’s next. Free memory used by temp node Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Deletion at the End head 5 8 -1 0 tail 2 16 3 7 NUL L Delete the node from the end Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Deletion at the End head 5 8 -1 0 temp X tail 2 16 3 7 NUL L Get the node pointed by X as temp Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Deletion at the End head 5 8 -1 0 tail temp 2 16 3 7 NUL L Point X’s next to temp’s next. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Deletion at the End head 5 8 -1 0 tail 2 16 3 NUL L Free memory used by temp node Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 NULL 5 2000 5000 5004 5008 5012 5016... 6024 6028... Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Freed Memory ( Can be re-allocated) Memory Visualization 8 3016 -1 4004 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 NULL 7 NULL 5 2000 5000 5004 5008 5012 5016... 6024 6028... Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Basic Operations: Deletion after position X head X 5 8 -1 0 tail 2 16 3 7 NUL L Delete after position 3 Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Deletion after position X head X temp 5 8 -1 0 tail 2 16 3 7 NUL L Get the node pointed by X as temp Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Deletion after position X head X temp 5 8 -1 0 tail 2 16 3 7 NUL L Point X’s next to temp’s next. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Basic Operations: Deletion after position X head X 5 8 -1 tail 2 16 3 7 NUL L Free memory used by temp node Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Freed Memory ( Can be re-allocated) Memory Visualization 8 3016 -1 4616 2000 2004 2008... 3016 3020 3024 3028... 0 4616 2 4800 16 5000 4004 4008... 4616 4620 4624... 4800 4804 3 5012 7 NULL 5 2000 5000 5004 5008 5012 5016... 6024 6028... Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing a Node Displaying Elements, Searching Elements Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Traverse to Node A Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Start from head Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Traverse to Next Node through next pointer Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Traverse to Next Node through next pointer Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Traverse to Next Node through next pointer Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Traverse to Next Node through next pointer Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Traverse to Next Node through next pointer Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Traverse to Next Node through next pointer Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Traversing Nodes in LL head 5 8 -1 0 A tail 2 16 3 7 NUL L Reached Node A Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering Dynamic Memory Allocation Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Static Memory Allocation Memory for named variables is allocated by the compiler. Exact size and type of storage must be known at compile time. For standard array declarations, this is why the size has to be constant. Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Dynamic Memory Allocation Memory allocated "on the fly" during run time Exact amount of space or number of items does not have to be known by the compiler in advance. For dynamic memory allocation, pointers are crucial Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Dynamic Memory Allocation in C Function Description malloc allocates the specified number of bytes realloc increases or decreases the size of the specified block of memory, moving it if necessary calloc allocates the specified number of bytes and initializes them to zero free releases the specified block of memory back to the system Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Self Referential Structure for LL struct node { int data; struct node *next; }; struct node *head=NULL,*newnode=NULL,*current; Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering  Doubly Linked Lists Downloaded Jacob P Cherian, Assistant fromofKtunotes.in Professor, Department CSE, Saintgits College of Engineering