Data Structures and Algorithms · Unit 5 · 8 hrs
Lists
Exam-focused notes for Lists (Data Structures and Algorithms, CSC211): what the TU syllabus asks and how it has actually been tested, with 11 solved past questions from this unit.
What this unit covers
- Basic Concept, List and ADT, Array Implementation of Lists, Linked List
- Types of Linked List: Singly Linked List, Doubly Linked List, Circular Linked List.
- Basic operations in Linked List: Node Creation, Node Insertion and Deletion from Beginning, End and Specified Position
- Stack and Queue as Linked List
Stack and Queue as Linked List
Define list. How can you use linked list to implement stack? Explain circular linked list.[10]
--- A list is a linear data structure that stores a collection of elements in a specific order. Each element in the list has a definite position (first, second, ..., last). There are two main ways to implement a list: - Contiguous List (Array-based): A larg...
Full solved answer →How can you use linked list to implement stack? Explain. [5]
A stack can be implemented using a singly linked list where each node contains a data field and a pointer to the next node. The top pointer always points to the most recently inserted (top) node of the stack. Using a linked list overcomes the fixed-size lim...
Full solved answer →Basic operations in Linked List
What is the algorithm for node insertion and deletion from specified position from doubly linked list. [5]
In a doubly linked list, each node has three fields: prev, info, and next. Steps: 1. Create a new node and set newnode-info = val 2. If head = NULL, then: - Set newnode-next = NULL - Set newnode-prev = NULL - Set head = newnode - Exit 3. If pos = 1 (insert ...
Full solved answer →How do you insert and delete a node at kth position of the doubly linked list? Describe the process of implementing stack and queue using linked list.[10]
--- A doubly linked list node has three fields: - prev -- pointer to previous node - info -- data field - next -- pointer to next node Step Action -------------- Step 1 Allocate memory for new node and assign data Step 2 If position is 1, insert at beginnin...
Full solved answer →What are benifits of using linked list over array? How can you insert a node in a singly linked list? [5]
--- Feature Linked List Array --------- Size Dynamic, grows/shrinks at runtime Fixed size, declared at compile time Insertion/Deletion Efficient (no shifting needed) Requires shifting of elements Memory Allocates memory as needed May waste memory if unused ...
Full solved answer →Types of Linked List
Explain circular linked list with example. How do you implement linked list operation in singly linked list? Explain.[10]
--- A circular linked list is a linked list in which the last node does not contain a NULL pointer. Instead, the link field of the last node points back to the first node of the list, forming a circle or loop. Every node in the list has a successor, and the...
Full solved answer →Differentiate between singly linked list and doubly linked list. How do you insert and delete a node from doubly linked list? Explain.[10]
--- Feature Singly Linked List Doubly Linked List --------- Node Structure Each node has two fields: info (data) and next (pointer to next node) Each node has three fields: info (data), next (pointer to next node), and prev (pointer to previous node) Direct...
Full solved answer →What do you mean by circular list? Differentiate between stack as a circular list and Queue as a circular list.[10]
A circular list is a linked list in which the last node points back to the first node, forming a closed loop or circle. Unlike a linear linked list where the last node points to NULL, in a circular list there is no NULL pointer -- every node has a successor...
Full solved answer →What do you mean by double linked list? Explain with example. [5]
A doubly linked list (also called a two-way linked list) is a linked list in which every node contains three fields: 1. PREV (Left Link) - a pointer that points to the previous node in the list 2. INFO (Data) - the actual data stored in the node 3. NEXT (Ri...
Full solved answer →Basic Concept, List and ADT, Array Implementation of Lists, Linked List
Explain array implementation of list. [5]
An array implementation of a list (also called an ArrayList) is a method of implementing a linear list using a one-dimensional array as the underlying storage structure. Elements are stored in contiguous (sequential) memory locations, and a variable (common...
Full solved answer →What is linked list? How is it different from array? [5]
A linked list is a linear data structure that defines a sequential set of elements (called nodes) in which each node stores two fields: 1. Info field - stores the actual data item 2. Link field - stores the pointer/address of the next node in the list The l...
Full solved answer →Make Unit 5 stick
Practice CSC211 with flashcards & quizzes