Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures and Algorithms > List, Linked Lists > Flashcards

List, Linked Lists Flashcards

1
Q

What’s a Linked List?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Advantages & Disadvantages of Linked List

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Singly Linked Lists - SLL

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

SLL Representation

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

SLL Operations

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Doubly Linked Lists - DLL

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

DLL Representation

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

DLL Operations

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Linked List on Array

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Singly Linked List on Array

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Doubly Linked List on Array

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a Sorted (Ordered) List?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the relation of a Sorted (Ordered) List?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the representation of a Sorted (Ordered) List?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the init operation of a Sorted (Ordered) List?

A 
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is the insert operation of a Sorted (Ordered) List?

A

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

17
Q

Explain some operations on a Sorted (Ordered) List.

A

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

18
Q

Explain some operations on a Sorted (Ordered) List.

A

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

Data Structures and Algorithms (11 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions