3) Advantages of Linked Lists Over Arrays:

Dynamic Size: Linked lists can easily grow or shrink in size as elements
are added or removed. In contrast, arrays often have a fixed size, and
resizing an array can be expensive.

Efficient Insertions and Deletions: Insertions and deletions of elements

within a linked list, especially in the middle, are more efficient compared to
arrays. This is because, in a linked list, you only need to update pointers to
insert or delete an element, while in an array, you may need to shift all
subsequent elements.

No Wasted Memory: Linked lists allocate memory dynamically for each

element, so there is no wasted memory due to unused slots, as in arrays
where you may have to allocate space for potential future elements.

Ease of Merging and Splitting: When merging or splitting two linked lists,
it can be done efficiently by updating a few pointers, while merging or
splitting arrays would require copying elements and resizing.

No Need for Preallocation: Linked lists don't require preallocation of

memory. You can add elements as needed, which can be beneficial when
you don't know the final size of your data in advance.

Disadvantages of Linked Lists Compared to Arrays:

Random Access: Linked lists do not support efficient random access to

elements. To access an element, you have to traverse the list from the
beginning, which can be slow for large lists. In contrast, arrays provide
constant-time access to any element based on its index.
Increased Memory Overhead: Linked lists use extra memory for storing
pointers/references in addition to the actual data. This can lead to
increased memory overhead compared to arrays.

Slower Traversal: Traversing a linked list can be slower than iterating over
an array due to the scattered nature of memory allocation in linked lists,
which can result in cache inefficiencies.

Not Cache-Friendly: Because elements in a linked list are not stored

sequentially in memory, cache locality is reduced, leading to potentially
slower performance for certain operations.

Complexity: Implementing and managing linked lists can be more complex

than arrays, especially for beginners. Debugging and maintaining linked list
code can be challenging.

7) Polynomial manipulations can be performed with lists by representing

each term of the polynomial as a sublist or as an element of a single list.
Using sublists:
Each sublist would contain the coefficient and exponent of the term. For
example, the polynomial 3x^2 + 2x + 1 could be represented as the
following list of sublists:
[[3, 2], [2, 1], [1, 0]]
Using a single list:
Each element of the list would be a term of the polynomial, in the form of
coefficient * x^exponent. For example, the polynomial 3x^2 + 2x + 1 could
be represented as the following list:
[3x^2, 2x, 1]
Once a polynomial is represented as a list, various operations can be
performed on it using standard list operations. For example:
Addition:
To add two polynomials, we can simply combine the corresponding terms
from each list. For example, to add the polynomials 3x^2 + 2x + 1 and x^2
+ 3x, we would combine the first terms, the second terms, and the third
terms, respectively. This would give us the following polynomial:
4x^2 + 5x + 1

Subtraction:
To subtract two polynomials, we can simply subtract the corresponding
terms from each list. For example, to subtract the polynomial x^2 + 3x from
the polynomial 3x^2 + 2x + 1, we would subtract the first terms, the second
terms, and the third terms, respectively. This would give us the following
polynomial:
2x^2 - 1x

Multiplication:
To multiply two polynomials, we can use the distributive property. For
example, to multiply the polynomials 3x^2 + 2x + 1 and x^2 + 3x, we would
multiply each term in the first polynomial by each term in the second
polynomial. This would give us the following polynomial:
3x^4 + 11x^3 + 7x^2 + 6x + 1

Division:
To divide two polynomials, we can use long division. For example, to divide
the polynomial 3x^4 + 11x^3 + 7x^2 + 6x + 1 by the polynomial x^2 + 3x,
we would use long division to get the following quotient and remainder:
Quotient: 3x^2 + 2x + 1
Remainder: 2
8) Insertion into a singly linked list
To insert an element into a singly linked list, we need to perform the
following steps:
1. Create a new node containing the element to be inserted.
2. Find the node before which the new node is to be inserted.
3. Make the next pointer of the new node point to the node after the
insertion point.
4. Make the next pointer of the insertion point point to the new node.

Deletion from a singly linked list

To delete an element from a singly linked list, we need to perform the
following steps:
1. Find the node to be deleted.
2. Make the next pointer of the node before the deleted node point to
the node after the deleted node.
3. Delete the deleted node.

Insertion into a doubly linked list

To insert an element into a doubly linked list, we need to perform the
following steps:
1. Create a new node containing the element to be inserted.
2. Find the node before which the new node is to be inserted.
3. Make the next pointer of the new node point to the node after the
insertion point.
4. Make the previous pointer of the new node point to the node before
the insertion point.
5. Make the next pointer of the insertion point point to the new node.
6. Make the previous pointer of the node after the insertion point point
to the new node.

Deletion from a doubly linked list

To delete an element from a doubly linked list, we need to perform the
following steps:
1. Find the node to be deleted.
2. Make the next pointer of the node before the deleted node point to
the node after the deleted node.
3. Make the previous pointer of the node after the deleted node point to
the node before the deleted node.
4. Delete the deleted node.

9) Insertion
To insert a new node into a cursor-based linked list, we perform the
following steps:
1. Move the cursor to the node before which the new node is to be
inserted.
2. Create a new node containing the element to be inserted.
3. Make the next pointer of the new node point to the node after the
insertion point.
4. Make the previous pointer of the new node point to the node before
the insertion point.
5. Make the next pointer of the insertion point point to the new node.
6. Make the previous pointer of the node after the insertion point point
to the new node.
Deletion
To delete a node from a cursor-based linked list, we perform the following
steps:
1. Move the cursor to the node to be deleted.
2. Make the next pointer of the node before the deleted node point to
the node after the deleted node.
3. Make the previous pointer of the node after the deleted node point to
the node before the deleted node.
4. Delete the deleted node.
10) • Music players: Linked lists are used to store playlists in music
players. Each song in the playlist is represented as a node in the linked list,
and the next pointer of each node points to the next song in the playlist.
This allows users to easily navigate between songs in the playlist.
• Image viewers: Linked lists are also used to store images in image
viewers. Each image is represented as a node in the linked list, and the
next pointer of each node points to the next image in the sequence. This
allows users to easily view images in order.
• Web browsers: Linked lists are used to implement the back and
forward buttons in web browsers. When a user clicks on the back button,
the browser uses a linked list to navigate to the previous page in the
browsing history. When a user clicks on the forward button, the browser
uses a linked list to navigate to the next page in the browsing history.
• Operating systems: Linked lists are used in operating systems to
implement various data structures, such as the memory management
system and the file system. For example, the memory management system
uses a linked list to keep track of free memory blocks. The file system uses
a linked list to represent the directory structure of a file system.
• Compilers: Linked lists are also used in compilers to implement
various data structures, such as the symbol table and the syntax tree. The
symbol table is a data structure that stores information about symbols, such
as variables and functions. The syntax tree is a data structure that
represents the structure of a program.

11) In a stack, insertion and deletion are performed using two fundamental
operations: "push" and "pop." A stack is a data structure that follows the
Last-In-First-Out (LIFO) principle, meaning that the most recently added
item is the first one to be removed.
1. Push Operation (Insertion):
The "push" operation is used to add (insert) an element onto the top of the
stack.
2. Pop Operation (Deletion):
The "pop" operation is used to remove (delete) the top element from the
stack.
•void push (stack *s, int element);
/* Insert an element in the stack */
•int pop (stack *s);
/* Remove and return the top element */