Linked List Flashcards
What is a linked list?
a Linked list is a linear collection of data elements, whose order is not given by their physical placement in memory.
In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence.
Why is it used?
This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration.
What is a drawback of it?
A drawback of linked lists is that access time is linear (and difficult to pipeline).
Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists.
What can they be used to implement?
They can be used to implement several other common abstract data types, including lists, stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement those data structures directly without using a linked list as the basis.
What is a principle benefit?
The principal benefit of a linked list over a conventional array is that the list elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk, while restructuring an array at run-time is a much more expensive operation.
When are they less optimal, O(n)?
since simple linked lists by themselves do not allow random access to the data or any form of efficient indexing, many basic operations—such as obtaining the last node of the list, finding a node that contains a given datum, or locating the place where a new node should be inserted—may require iterating through most or all of the list elements.
What are the disadvantages?
They use more memory than arrays because of the storage used by their pointers.
Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
Nodes are stored incontiguously, greatly increasing the time periods required to access individual elements within the list, especially with a CPU cache.
Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards[1] and while doubly linked lists are somewhat easier to read, memory is consumed in allocating space for a back-pointer.
What is the code to add a new node?
node addNode(node head, int value){
node temp,p;// declare two nodes temp and p
temp = createNode();// assume createNode creates a new node with data = 0 and next pointing to NULL.
temp->data = value; // add element's value to data part of node
if(head == NULL){
head = temp; //when linked list is empty
}
else{
p = head;//assign head to p
while(p->next != NULL){
p = p->next;//traverse the list until p is the last node.The last node always points to NULL.
}
p->next = temp;//Point the previous last node to the new node created.
}
return head;
}
What are the fields?
The field of each node that contains the address of the next node is usually called the ‘next link’ or ‘next pointer’. The remaining fields are known as the ‘data’, ‘information’, ‘value’, ‘cargo’, or ‘payload’ fields.
Doubly linked-lists?
In a ‘doubly linked list’, each node contains, besides the next-node link, a second link field pointing to the ‘previous’ node in the sequence. The two links may be called ‘forward(‘s’) and ‘backwards’, or ‘next’ and ‘prev’(‘previous’).
What is the code for a linked list to spell out FISH?
Node1.data = "F" Node1.next = Node2 Node2.data = "I" Node2.next = Node3 Node3.data = "S" Node3.next = Node4 Node4.data = "H" Node4.next = null
How to insert data in a double-linked list?
Node6.data = "6" Node6.previous = Node2 Node6.next = Node3 Node3.previous = Node6 Node2.next = Node6
