List, Linked Lists Flashcards
What’s a Linked List?
- linear data structure that consists of nodes (sometimes called links)
- each node contains:
- the data (that we store in the linked list)
- a pointer to the address of the next node
(and possibly a pointer to the address of the previous node) - the order of the elements is determined by a pointer which is placed in each element
- the nodes are not necessarily adjacent in the memory,
this is why we need to keep the address of the successor in each node - elements accessed based on the pointers stored in the nodes
- directly access only the first element (and maybe the last one) of the list
- iterating through all the elements of a linked list we have two options:
- use an iterator
- use a for loop & the getElement subalgorithm
Advantages & Disadvantages of Linked List
Advantages:
- No memory is used for non-existing elements.
- Constant time operations at the beginning of the list.
- Elements are never moved (important if copying an element takes a lot of time).
Disadvantages of Linked Lists
- We have no direct access to an element from a given position
(however, iterating through all elements of the list using an iterator has Θ(n) time complexity).
- Extra space is used up by the addresses stored in the nodes.
- Nodes are not stored at consecutive memory locations
(no benefit from modern CPU caching methods).
Singly Linked Lists - SLL
- a linked list, where each node from the list contains the data and the address of the next node
- the first node of the list => head of the list
- the last node of the list => tail of the list
- the tail of the list contains the special value NIL as the address of the next node (which does not exist)
- if the head of the SLL is NIL, the list is considered empty
SLL Representation
SLL Operations
Doubly Linked Lists - DLL
- a linked list, where each node from the list contains the data,
the address of the next node & the address of the previous node as well - similar to a singly linked list, (besides the next link, we have a prev link as well)
- the prev link of the first element and the next link of the last element is set to NIL
- we can walk through the elements of the list in both directions
(if we have a node from a DLL, we can go to the next node or to the previous node) - the tail of the list contains the special value NIL as the address of the next node (which does not exist)
- if the head of the SLL is NIL, the list is considered empty
DLL Representation
DLL Operations
Linked List on Array
Singly Linked List on Array
Doubly Linked List on Array
What is a Sorted (Ordered) List?
- a list
- the elements from the nodes are in a specific order
- order is given by a relation
- we will keep the relation used for ordering the elements as part of the
structure, we will have a field that represents this relation - using an abstract relation will give us more flexibility:
- we can easily change the relation
(without changing the code written for the sorted linked list)
- we can have, in the same application,
lists with elements ordered by different relations
What is the relation of a Sorted (Ordered) List?
- we can imagine the relation as a function with two parameters
(two TComp elements)true, ”c1 ≤ c2” relation(c1, c2) = ( false, otherwise - ”c1 ≤ c2” means that c1 should be in front of c2 when ordering the elements
What is the representation of a Sorted (Ordered) List?
Sorted singly linked list - SSLL
SSLLNode:
info: TComp
next: ↑ SSLLNode
SSLL:
head: ↑ SSLLNode
rel: ↑ Relation
Sorted doubly linked list - SDLL
SDLLNode:
info: TComp
next: ↑ SDLLNode
prev: ↑ SDLLNode
SDLL:
head: ↑ SDLLNode
tail: ↑ SDLLNode
rel: ↑ Relation
What is the init operation of a Sorted (Ordered) List?
Sorted singly linked list - SSLL
Complexity: Θ(1)
subalgorithm init (ssll, rel) is:
// pre: rel is a relation
// post: ssll is an empty SSLL
ssll.head ← NIL
ssll.rel ← rel
end-subalgorithm
Doubly singly linked list - SDLL
Complexity: Θ(1)
subalgorithm init (sdll, rel) is:
// pre: rel is a relation
// post: sdll is an empty SDLL
sdll.head ← NIL
sdll.tail ← NIL
sdll.rel ← rel
end-subalgorithm
What is the insert operation of a Sorted (Ordered) List?
Sorted singly linked list - SSLL
- we need to find the node after which we insert the new element
(otherwise we cannot set the links correctly)
- the node we want to insert after is the first node whose successor is greater
than the element we want to insert (where greater than is represented by the
value false returned by the relation)
- 2 special cases:
- an empty SSLL list
- when we insert before the first node
Complexity: O(n)
subalgorithm insert (ssll, elem) is:
// pre: ssll is a SSLL; elem is a TComp
// @post: the element elem was inserted into ssll to where it belongs
newNode ← allocate()
[newNode].info ← elem
[newNode].next ← NIL
if ssll.head = NIL then
// the list is empty
ssll.head ← newNode
else if ssll.rel(elem, [ssll.head].info) then
//elem is ”less than” the info from the head
[newNode].next ← ssll.head
ssll.head ← newNode
else
cn ← ssll.head // cn - current node
while [cn].next != NIL and ssll.rel(elem, [[cn].next].info) false execute
cn ← [cn].next
end-while
//now insert after cn
[newNode].next ← [cn].next
[cn].next ← newNode
end-if
end-subalgorithm
Sorted doubly linked list - SDLL
Explain some operations on a Sorted (Ordered) List.
Sorted singly linked list - SSLL
Search operation
- similar to the search operation for a SLL (except that we can stop looking for
the element when we get to the first element that is ”greater than” the one
we are looking for)
Delete operation
- identical to the same operations for a SLL (except that the search part can
use the relation and stop sooner if the element we want to remove is not in
the SSLL)
Return an element from a position operation
- identical to the same operation for a SLL
Iterator
- identical to the iterator to a SLL
Sorted doubly linked list - SDLL
Explain some operations on a Sorted (Ordered) List.
Insert elements (using positions)
Remove elements (using positions)
Access the successor and predecessor of an element from a given position
Access an element from a position
