Data Structures & Algorithms - Linked Lists PDF

Data Structure & Algorithm LINKED LIST BY: MOHAMMED L. MAHMOOD [email protected] FALL – 2024/2025  INTRODUCTION Lists Definition Lists is a group of objects which is organized in sequence. List categories: linear list and nonline...

Data Structure & Algorithm LINKED LIST BY: MOHAMMED L. MAHMOOD [email protected] FALL – 2024/2025  INTRODUCTION Lists Definition Lists is a group of objects which is organized in sequence. List categories: linear list and nonlinear list. Linear list – a list in which the data is organized in sequence, example: array, linked list, stack and queue Non-Linear list – a list in which the data is stored not sequence, example: tree and graph 3  Introduction to Linear List Array and linked lists are linear lists that doesn’t have any restrictions while implementing operations such as, insertion, deletion and accessing data in the lists. The operations can be done in any parts of the lists, either in the front lists, in the middle or at the back of the lists. Stack and queue is a linear lists that has restrictions while implementing its operations. Stack – to insert, delete and access data can only be done at the top of the lists. Queue - Insert data in a queue can be done at the back of the lists while to delete data from a queue can only be done at the front list.  Introduction to Linear List Below is an array named Places An array named Places which contains attributes placeName, region, and yearEstablished. The array is sorted and can only be accessed based on the index or subscript of the array. Example: to access information for a place named York, we can use: Places.placeName, Places.region, Places.yearEstablished.  Introduction to Linear List Linked lists which contain several nodes which is sorted in ascendeng order. Each node contains at least A piece of data (any type) Pointer to the next node in the list Need pointer variable Head [Senarai]: to point to the first node  Introduction to Linear List Basic operations for linear lists: Insert new data in the lists. Delete data from a lists. Update data in the list. Sort data in the lists and Find data in the list.  Array as linear list Sized is fixed during array declaration. Data insertion is limited to array size In order to insert data, need to check whether the array is full or not. If the array is full, the insertion cannot be done. Array Implementation...the drawbacks Requires an estimate of the maximum size of the list □ waste space printList and find: linear access findKth: constant insert and delete: slow insert at position 0 (making a new element) requires first pushing the entire array down one spot to make room delete at position 0 requires shifting all the elements in the list up one On average, half of the lists needs to be moved for either operation  Array Implementation...the drawbacks 9. Need space to insert item in the middle of the list. Insert Fatimah Adam in between students named Durrani Nukman and Mohd Saufi. insert at index 3 : requires first pushing the entire array from index 3 down one spot to make room Array Implementation...the drawbacks 10 New item is inserted at index 3, after shifting the data from index 3 onwards.. Array Implementation...the drawbacks To delete item in the middle of the array will leave a blank space in the middle. It requires shifting all the elements in the list up one in order to eliminate the space.. Example: when information about Durrani Nukman is deleted, all elements below it, is shifted up.  Pointer Implementation (Linked List) Ensure that the list is not stored contiguously use a linked list a series of structures that are not necessarily adjacent in memory □Each node contains the element and a pointer to a structure containing its successor □the last cell’s next link points to NULL □ Compared to the array implementation, □the pointer implementation uses only as much space as is needed for the elements currently on the list □but requires space for the pointers in each cell  Linked list variations Singly linked list Doubly linked list Circular linked list Circular doubly linked list Sorted linked list Unsorted linked list  Singly Linked Lists A B C  Head A linked list is a series of connected nodes Each node contains at least A piece of data (any type) Pointer to the next node in the list node Head: pointer to the first node A The last node points to NULL data pointer  Variations of Linked Lists Circular linked lists The last node points to the first node of the list A B C Head How do we know when we have finished traversing the list? (Tip: check if the pointer of the current node is equal to the head.)  Variations of Linked Lists Doubly linked lists Each node points to not only successor but the predecessor There are two NULL: at the first and last nodes in the list Advantage: given a node, it is easy to visit its predecessor. Convenient to traverse lists backwards  A B C  Head  Variations of Linked Lists Circular doubly linked list No NULL value at the first and last nodes in the list Convenient to traverse lists backwards and forwards  Variations of Linked Lists Sorted Linked list : The nodes in the lists is sorted in certain order. D F K  Head UnSorted Linked list : The nodes in the lists is not sorted in any order. W M P  Head  Array versus Linked Lists Linked lists are more complex to code and manage than arrays, but they have some distinct advantages. Dynamic: a linked list can easily grow and shrink in size. We don’t need to know how many nodes will be in the list. They are created in memory as needed. In contrast, the size of a C++ array is fixed at compilation time. To insert or delete an element in an array, we need to copy to temporary variables to make room for new elements or close the gap caused by deleted elements. With a linked list, no need to move other nodes. Only need to reset some pointers.