Vectors, Lists and Sequences
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Vector -ADT
•The Vector ADT extends the notion of array by storing a sequence of arbitrary objects
•An element can be accessed, inserted or removed by specifying its rank (number of elements
preceding it)
•Main vector operations:
•object elemAtRank(integer r): returns the element at rank r without removing it
•object replaceAtRank(integer r, object o): replace the element at rank with o and return the old
element
•insertAtRank(integer r, object o): insert a new element o to have rank r
•object removeAtRank(integer r): removes and returns the element at rank r
•Additional operations size() and isEmpty()

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Vector - ADT
•An exception is thrown if an incorrect rank is specified (e.g., a negative rank)
•Direct applications
•Sorted collection of objects (elementary database)
•Indirect applications
•Auxiliary data structure for algorithms
•Component of other data structures

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Array-based Vector
•Use an array V of size N
•A variable n keeps track of the size of the vector (number of elements stored) •Operation
elemAtRank(r) is implemented in O(1) time by returning V[r]
•In the array based implementation of a Vector
•The space used by the data structure is O(n)
•size, isEmpty, elemAtRank and replaceAtRank run in O(1) time
•insertAtRank and removeAtRank run in O(n) time
•
•
V
0
1
2
n
r

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
List – ADT
•The List ADT models a sequence of positions storing arbitrary objects
•It establishes a before/after relation between positions
•
•
•Update methods:
•replaceElement(p, o), swapElements(p, q), insertBefore(p, o), insertAfter(p, o), insertFirst(o),
insertLast(o), remove(p)
•

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
List
•Single linked list
•Each node stores
•element
•link to the next node
•For implementation of stack  (O(n) for memory , O(1) each operation) and queue (O(n) memory, O(1)
each operation)
•Double linked list
•Nodes implement Position and store:
•element
•link to the previous node
•link to the next node
next
elem
nodel
prev
next
elem
node

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Sequence - ADT
•The Sequence ADT is the union of the Vector and List ADTs
•Elements accessed by Rank, or Position
•Generic methods:
•size(), isEmpty()
•Vector-based methods:
•elemAtRank(r), replaceAtRank(r, o), insertAtRank(r, o), removeAtRank(r)
•List-based methods:
•first(), last(), before(p), after(p), replaceElement(p, o), swapElements(p, q), insertBefore(p,
o), insertAfter(p, o), insertFirst(o), insertLast(o), remove(p)
•Bridge methods:
•atRank(r), rankOf(p)

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Sequence
•The Sequence ADT is a basic, general-purpose, data structure for storing an ordered collection of
elements
•Direct applications:
•Generic replacement for stack, queue, vector, or list
•small database (e.g., address book)
•Indirect applications:
•Building block of more complex data structures