Data Structures: Linked Lists

Question 1

What is the purpose of a linked list?

Answer 1

a linked list is a dynamic arrangement of nodes that can grow and shrink at runtime. Therefore, it is useful when you do not know the initial size of the data. where each node contains a link to the next node in the list. These ‘links’ are pointers

Question 2

What are the advantages of a linked list?

Answer 2

Dynamic data structure

Resizable at runtime

efficient and easily implemented insertion and deletion functions

Question 3

When do we use a linked list over a list/array?

Answer 3

When implementing a queue, in which elements are continuously inserted or removed from the beginning of the list

Question 4

How does a linked list work?

Question 5

What is the structure of a linked list?

Answer 5

a linked list consists of Nodes. Each node contains two components: data and a pointer to the next node.

The last node in the linked list points to NONE or NULL
The first node in the linked list is the HEAD

Question 6

All data structures have unique strengths and weaknesses. Therefore, it is important to know these strengths/weaknesses when it comes to designing, optimizing, and scaling programs

So, the strengths and weaknesses of a linked list are:

Answer 6

The strengths of the linked list:

+ The linked list has two operations, insertion and deletion, that are efficient and easy to implement
+ linked list has dynamic data structure that can grow and shrink at runtime
+ no memory wastage

Question 7

Why are linked lists used?

Answer 7

linked lists are often used because insertion and deletion are efficient and easy to implement

Linked lists are used for queues, stacks, and other abstract data types

Question 8

What are the disadvantages of linked lists?

Answer 8

Memory usage: more memory usage is required in a linked list than an array/list since each node stores both data and a pointer to the next node

Traversal: it is more time-consuming to traverse a linked list than an array since you have to traverse all n elements to access the nth element. Whereas with an array, you can directly access the nth element

Reverse Traversing: is not possible on a singly linked list and requires a doubly linked list, which stores an additional pointer in the node. This pointer points to the address of the previous node. Thus, there is a wastage of memory

Random Access: poor performance as a result of random memory storage. The data can be stored far apart, which makes it difficult for the CPU to cache the contents of a linked list, which results in poor performance