Linked Lists Flashcards
is an arrays capacity fixed or variable?
fixed
When adding elements to a linked list and taking away from a linked list what must happen?
in order to add an element you move everything after the index you are adding to, to the right, and when taking away elements you must moved every element after the index you are removing from to the left to fill the gap.
what is the head of a linked list?
head stores the link to the first node
what is in the node in the linked list?
the element is in the node and the node also contains the link to the next stored load or contains the end of the list marker.
what are the pros to linked lists?
not fixed capacity
we allocate memory only when needed
the size of ta link list is only limited by the memory free in the heap
what are the cons of linked lists
The code to build a linked list is more complicated than the
code to declare or dynamically allocate an array
Required steps: allocate a node, store the payload in
the node, update the link to the next node
Must ensure that the last node’s link contains the end-
of-list marker
how do you create a linked list containing a single node
Step 1: Declare the node type
typedef struct node {
int data;
struct node *next;
} node_t;
Step 2: Declare the head (i.e., create a pointer to the head)
node_t *head;
Step 3: Allocate memory for the node (the node is stored in the heap)
head = malloc(sizeof(node_t));
assert(head != NULL);
what does it mean when the head of the list is equal to NULL
it means that the linked list has no nodes.
What is a linked list in computer science?
A linked list is a data structure that allows storing a collection of elements where the order of elements matters, and each element’s position is given by its rank or index.
How are elements stored in a linked list compared to arrays?
Elements in a linked list are not stored in contiguous memory like arrays. Each element in a linked list is grouped with a link to the next element, forming a chain-like structure.
What terminology is used to describe the structure of a linked list where each node is linked to one other node?
This type of linked list is referred to as a singly-linked list.
What are the pros of using linked lists?
Linked lists have dynamic memory allocation, allowing for a theoretically unlimited size. They are also flexible in terms of insertion and deletion operations compared to arrays.
What are some cons associated with linked lists?
Building a linked list requires more complex code compared to declaring or dynamically allocating an array. Additionally, accessing elements in a linked list is less efficient than in arrays since traversal is necessary.
How are nodes typically declared in C for implementing linked lists?
Nodes are typically declared using a struct, where each node contains a payload (data) and a pointer to the next node in the list.
What is the purpose of the assert function in C programming, especially concerning memory allocation?
The assert function is used to verify assumptions made during the program’s execution. It’s commonly used after memory allocation to ensure that memory allocation was successful before proceeding with further operations.
How can you create a linked list containing one node in C?
You can create a linked list containing one node by declaring a node type, allocating memory for the node, initializing its payload and link, and finally setting the head pointer to point to this node.
How can you create an empty linked list in C?
An empty linked list is represented by a head pointer containing NULL, indicating that it doesn’t point to any node.
what are the steps to creating a new node at the beginning of a linked list?
- initialize the content of the new element
- Point new node point to the old head
- point the head to the inserted node
What is a pushing or push function?
function that inserts an integer at the front of a linked list
What are the three steps involved in inserting a new node at the front of a linked list?
The three steps are: allocating a new node and initializing its payload, setting up the link of the new node to point to the current first node, and updating the head pointer to point to the new node.
What is the purpose of the assert function in the context of allocating memory for a new node in a linked list?
The assert function is used to verify that memory allocation was successful before proceeding with further operations. It ensures that the pointer returned by malloc is not NULL, indicating successful allocation.
How can you apply the 3-step link-in technique to insert a new node at the front of a linked list?
You can allocate a new node, set its next pointer to the current head of the list, and then update the head pointer to point to the new node.
Why is it important to use memory diagrams when understanding or designing linked list code?
Memory diagrams help visualize the state changes that occur during the execution of linked list code, especially since linked lists involve dynamic memory allocation and deallocation.
What is the correct approach to designing a new linked list function?
When designing a new linked list function, it’s important to draw “before and after” diagrams to visualize the state changes required, considering different cases such as an empty list, a list with one node, and a list with multiple nodes.
