Introduction to linked list in data structure.pptx

Introduction to linked list in data structure

1. Linear Data structure and Linked list operations using C++ Prepared by Dr. Princy Diwan Assistant Professor (Sr. Grade)

2. Linear Data Structure A linear data structure is a type of data structure that stores the data linearly or sequentially. Every element makes a connection to only its previous and next elements. Examples: Array, stack, queue, LinkedList The linked allocation has the following draw backs: No direct access to a particular element. Additional memory required for pointers.

3. Array versus Linked Lists Arrays are suitable for: Inserting/deleting an element at the end. Randomly accessing any element. Searching the list for a particular value. Linked lists are suitable for: Inserting an element. Deleting an element. Applications where sequential access is required. In situations where the number of elements cannot be predicted beforehand.

4. Linked List Linked lists and arrays are similar since they both store collections of data. The array's features all follow from its strategy of allocating the memory for all its elements in one block of memory. Linked lists use an entirely different strategy: linked lists allocate memory for each element separately and only when necessary.

5. Linked lists Like arrays, 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. Linked lists are appropriate when the number of data elements to be represented in the data structure at once is unpredictable. Linked lists are dynamic, so the length of a list can increase or decrease as necessary.

6. W h y Lin k ed List? Arrays can be used to store linear data of similar types, but arrays have the following limitations. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage. Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted.

7. Types of Linked List

8. Traversing A linked list is a linear data structure that needs to be traversed starting from the head node until the end of the list. Unlike arrays, where random access is possible, linked list requires access to its nodes through sequential traversal. Traversing a linked list is important in many applications. For example, we may want to print a list or search for a specific node in the list. Or we may want to perform an advanced operation on the list as we traverse the list. The algorithm for traversing a list is fairly trivial. Start with the head of the list. Access the content of the head node if it is not null. Then go to the next node(if exists) and access the node information Continue until no more nodes (that is, you have reached the last node) Let LIST be a linked list in memory stored in linear array INFO and LINK with START pointing to the first element and NULL indicating the end of LIST. Suppose we want to traverse LIST in order to Process each node exactly once. This section presents an algorithm that does so and then uses the algorithm in some applications.

9. Traversing

10. Basic Linked List Operations List Traversal Searching a node Insert a node Delete a node

11. Header Nodes One problem with the basic description: it assumes that whenever an item x is removed (or inserted) some previous item is always present. Consequently, removal of the first item and inserting an item as a new first node become special cases to consider. In order to avoid dealing with special cases: introduce a header node (dummy node) . A header node is an extra node in the list that holds no data but serves to satisfy the requirement that every node has a previous node.

12. List with a header node