ALGORITHMS DATA STRUCTURE AND ALGORITHMS • Lecture Division Week No.4 • Department BS CYB/3rd Semester • Instructor Engineer Ashna Batool DEFINITION OF LINKED LIST
• A linked list is a linear data structure consisting of a sequence of
elements, where each element (called a node) contains two main components: Data: The value or information stored in the node. Pointer (or Reference): A link to the next node in the sequence (or, in the case of a doubly linked list, links to both the next and previous nodes). BASIC COMPONENTS
Node: The fundamental part of a linked list. Each node contains:
Data: The value stored in the node. Pointer/Reference: A link to the next node in the list. Head: The first node in the linked list. If the list is empty, the head is usually set to null or None. Tail: The last node in the list, which points to null or None. LINKED LIST KEY CHARACTERISTICS
Dynamic Size: Unlike arrays, linked lists can grow and shrink in size dynamically as elements are added or removed. Non-contiguous Memory: Nodes may not be stored in contiguous memory locations, allowing for more flexible memory usage. Efficient Insertions/Deletions: Inserting or deleting nodes can be done efficiently (in constant time) if the position is known, as it only involves changing pointers. TYPES TYPES OF LINKED LISTS
Singly Linked List: Each node points to the next node, with no reference to the previous node. Doubly Linked List: Each node contains references to both the next and the previous nodes, allowing traversal in both directions. Circular Linked List: The last node points back to the first node, forming a circle. This can be singly or doubly linked SINGLY LINKED LIST
• A singly linked list is a simple data structure where each item (node) contains data and a reference (or link) to the next item in the list. This makes it easy to add or remove items without needing to shift the entire structure, as you might with an array. DOUBLY LINKED LIST
• A doubly linked list is a type of linked list where each node contains a reference to both the next node and the previous node, allowing for bidirectional traversal. This structure makes certain operations easier, such as inserting and deleting nodes. CIRCULAR LINKED LIST
• A circular linked list is a variation of the linked list in which the last node points back to the first node, creating a circular structure. This allows for continuous traversal of the list without the need to check for null pointers, as you can keep moving from one node to the next indefinitely. OPERATIONS Linked lists support various operations, each with its own time complexity. Here are some common operations: Insertion: • At the beginning: O(1) • At the end: O(n) for singly linked lists (O(1)) for doubly linked lists if you maintain a tail pointer) • At a specific position: O(n) OPERATIONS
Deletion: • From the beginning: O(1) • From the end: O(n) for singly linked lists (O(1) for doubly linked lists if you maintain a tail pointer) • From a specific position: O(n) OPERATIONS
Traversal: O(n) — visiting each node to access or display data.
Search: O(n) — finding an element by traversing the list. Reversal: O(n) — reversing the order of nodes in the list. Merging: O(n) — combining two sorted linked lists into one sorted list. Sorting: O(n log n)__ for algorithms like merge sort applied to linked lists. OPERATIONS IMPLEMENTATION LINKED LIST CLASS IMPLEMENTATION ADDING ELEMENTS TO LINKED LIST OUTPUT INSERT AT BEGINNING OUTPUT INSERT AT END OUTPUT SIZE HOW TO GET SIZE OF LINKED LIST OUTPUT DELETION OUTPUT ITERATIVE METHOD FOR LINKED LIST OUTPUT REVERSE METHOD OUTPUT SEARCHING OUTPUT SORTING OUTPUT COMPARISON
• Here's a simple comparison of different linked list algorithms in Java:
APPLICATIONS 1. Dynamic Memory Allocation Linked lists allow for dynamic memory allocation, which is useful when the size of the data structure needs to change frequently during runtime. 2. Implementation of Stacks and Queues • Stacks: Linked lists can be used to implement stacks, supporting operations like push and pop. • Queues: Similarly, linked lists can implement queues, supporting enqueue and dequeue operations efficiently. APPLICATIONS
3. Undo Functionality in Applications
Many applications, such as text editors, use linked lists to implement an undo feature, where each action is stored as a node, allowing users to traverse back through their actions. 4. Graph Representation Linked lists are used to represent graphs, where each node (vertex) has a linked list of adjacent nodes (edges). This adjacency list representation is space-efficient for sparse graphs. APPLICATIONS 5. Polynomial Representation In mathematical computations, polynomials can be represented using linked lists, where each node represents a term of the polynomial, storing coefficients and exponents. 6. Music Playlist Management Music players can use linked lists to manage playlists, allowing easy addition, deletion, and traversal through songs. APPLICATIONS 7. File System Implementation Linked lists can be used in file systems to manage file allocation blocks, linking together blocks of data that may not be contiguous. 8. Navigating Browser History Web browsers often use linked lists to manage browsing history, where each page visited is a node, allowing users to navigate back and forth. APPLICATIONS 9. Hash Tables with Chaining In hash tables, linked lists can be used to handle collisions. Each bucket of the hash table can contain a linked list of entries that hash to the same index. 10. Real-Time Simulation In real-time simulations (like video games), linked lists can manage active objects, allowing efficient addition and removal as objects enter and leave the scene. PROS AND CONS
• Pros: Dynamic size. Efficient insertions/deletions. • Cons: More memory usage per element due to pointers. Random access is not possible; traversal is required to find elements. NEXT WEEK TOPICS
Stacks • • Basics of Stack data structure • • Algorithms (Push, Pop, Peek) • • Implementation using Arrays • • Implementation using Linked Lists • • Expression parsing using Stacks (infix, prefix, postfix)
