DATA STRUCTURES AND LINKED LISTS IN C.pptx
- 1. DATA STRUCTURES ANDLINKED LISTS IN C
- 2. DATA STRUCTURES INC • The data structure name indicates itself that organizing the data in memory. • There are many ways of organizing the data in the memory as we have already seen one of the data structures, i.e., array in C language. • It is a set of algorithms that we can use in any programming language to structure the data in the memory.
- 3.
- 4. TYPES • Primitive Datastructure The primitive data structures are primitive data types. The int, char, float, double, and pointer are the primitive data structures that can hold a single value. • Non-Primitive Data structure The non-primitive data structure is divided into two types: 1. Linear data structure 2. Non-linear data structure
- 5. TYPES • Linear datastructure 1. The arrangement of data in a sequential manner is known as a linear data structure. 2. The data structures used for this purpose are Arrays, Linked list, Stacks, and Queues. 3. In these data structures, one element is connected to only one another element in a linear form. • Non-linear data structure 1. When one element is connected to the 'n' number of elements known as a non-linear data structure. 2. The best example is trees and graphs. 3. In this case, the elements are arranged in a random manner.
- 6. TYPES • Data structurescan also be classified as: 1. Static data structure: It is a type of data structure where the size is allocated at the compile time. Therefore, the maximum size is fixed. However, the values of the elements stored are not static and can be modified at any time. Example - Array. 2. Dynamic data structure: It is a type of data structure where the size is allocated at the run time. Therefore, the maximum size is flexible. Example - Linked List.
- 7. OPERATIONS ON DATASTRUCTURES • Searching: We can search for any element in a data structure. • Sorting: We can sort the elements of a data structure either in an ascending or descending order. • Insertion: We can also insert the new element in a data structure. • Update: We can also update the element, i.e., we can replace the element with another element. • Deletion: We can also perform the delete operation to remove the element from the data structure.
- 8. LINKED LISTS • Likearrays, Linked List is a linear data structure. • Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers. • They includes a series of connected nodes. • Here, each node stores the data and the address of the next node.
- 9. USES • The listis not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space. • list size is limited to the memory size and doesn't need to be declared in advance. • Empty node can not be present in the linked list. • We can store values of primitive types or objects in the singly linked list.
- 10. SINGLY LINKED LIST •Singly linked list can be defined as the collection of ordered set of elements. • The number of elements may vary according to need of the program. • A node in the singly linked list consist of two parts: data part and link part. • Data part of the node stores actual information that is to be represented by the node while the link part of the node stores the address of its immediate successor. • One way chain or singly linked list can be traversed only in one direction.
- 11. DOUBLY LINKED LIST •Doubly linked list is a complex type of linked list in which a node contains a pointer to the previous as well as the next node in the sequence. • Therefore, in a doubly linked list, a node consists of three parts: node data, pointer to the next node in sequence (next pointer) , pointer to the previous node (previous pointer). • The prev part of the first node and the next part of the last node will always contain null indicating end in each direction. • Due to the fact that, each node of the list contains the address of its previous node
- 12. CIRCULAR LINKED LIST •In a circular Singly linked list, the last node of the list contains a pointer to the first node of the list. • We can have circular singly linked list as well as circular doubly linked list. • We traverse a circular singly linked list until we reach the same node where we started. • The circular singly liked list has no beginning and no ending. There is no null value present in the next part of any of the nodes.
- 13. CIRCULAR DOUBLY LINKEDLIST • Circular doubly linked list is a more complexed type of data structure in which a node contain pointers to its previous node as well as the next node. • Circular doubly linked list doesn't contain NULL in any of the node. • The last node of the list contains the address of the first node of the list. • The first node of the list also contain address of the last node in its previous pointer
- 14. INSERTING A NODE •A node can be added in three ways 1. At the front of the linked list 2. After a given node. 3. At the end of the linked list.
- 15. DELETING A NODE •Delete from Beginning: Point head to the next node i.e. second node head = head->next • Delete from end: Point head to the previous element i.e. last second element. Change next pointer to null struct node*temp = head; while(temp->next->next!=NULL) { temp = temp->next } temp->next = NULL
- 16. DELETING A NODE •Delete from Middle: Traverse to element before the element to be deleted Change next pointer to exclude the node from the chain for(int i=2; i< position; i++) { if(temp->next!=NULL) { temp = temp->next; } } temp->next = temp->next->next;