3.3 Elementary Data Structures: Linked Lists Flashcards
What are Linked Lists?
A linked list is a set of items where each item is a part of a node that also contains a link to a node. In other words, each item contains the information we need to get to the next item.
What advantage do linked lists have over arrays?
Linked lists provide us with the ability to easily rearrange the items efficiently. Eg. to add an element in the front of an array: O(N), the same for a linked list: O(1).
What disadvantage do linked lists have over arrays?
The ease of modification/rearrangement that linked lists provide comes with a cost: quick access to any arbitrary item in the list, because the only way to get to an item is to follow links from the start. LINKED LISTS: SEQUENTIAL ACCESS. ARRAYS: RANDOM ACCESS.
Why are linked lists called SELF-REFERENT structures?
Because nodes in a linked lists are defined in terms of references to nodes.
Why are linked lists called CYCLIC STRUTURES?
Because although the nodes generally contain references to other nodes, they can also contain a reference to themselves.
What are the three conventions to represent the link for the last item in a linked list?
- It could be a NULL LINK that points to no node.
- It could be a DUMMY LINK that points to a dummy node that contains no item.
- It could be a refer back to the first node, making a list a CIRCULAR LIST.
What are one-dimensional lists?
One-dimensional lists are lists in which all nodes, except perhaps the first and last one have only one link referring TO them.
Give a typedef declaration for a structure representing a linked list, and explain all its components.
typedef struct node *link;
struct node {Item item; link next; };
Links are references to nodes, and nodes consist of items and links. Items are of an unspecified datatype Item. This Item can be made to fit any datatype using a typedef statement.
How to allocate memory for a node/link? Give a C statement.
link x = malloc(sizeof(*x));
How to refer to item and link parts of a node x?
(x).item and (x).link
or
x->item and x->link
Write code to insert a node t after a node x.
t->next = x->next; x->next = t;
Write code to delete a node which follows a node x.
x->next = x->next->next;
Why is insertion and deletion easier in linked lists than in arrays?
Insertion and deletion is difficult in arrays because we need to move all the elements following the affected element in an array. So, insertion and deletion is a O(N) time operation.
In linked lists, we simply need to rearrange the pointers, so it is a O(!) time operation.
Why is finding the kth (finding an element given its index) a difficult operation in linked lists, compared to arrays.
To reach an element with the index k in a linked list, due to sequential access, we need to follow k links. This makes accessing elements a O(N) time operation.
In arrays, we can randomly access an element with its index in O(1) time, like a[k].
Why is finding an element before a given item an unnatural operation on singly linked lists?
Because there is no way to access an element which comes before an element, ie, there is no pointer which points backward from a given element.
