Problems with Arrays
• An array is a contiguous storage that provides insufficient abstractions for handling addition and deletion of elements.
• Addition and deletion require n/2 shifts on average.
• The computation time is O(n). • Resizing affects performance.
211
© Dr Markus Lumpe, 2021
Deletion Requires Relocation
Delete 5
29 20 4
3
5
29
20
4
3
29
20
4
212
© Dr Markus Lumpe, 2021
Insertion Requires Relocation
Insert 50 after 29
20 4
3
29
20
4
3
29
50
20
4
213
© Dr Markus Lumpe, 2021
Singly-Linked Lists
• A singly-linked list is a sequence of data items, each connected to the next by a pointer called next.
• A data item may be a primitive value, a composite value, or even another pointer.
• A singly-linked list is a recursive data structure whose nodes refers to nodes of the same type.
Data
Data
Data
Nil
214
© Dr Markus Lumpe, 2021
Impossible Singly-Linked List Structure in C++:
X= X ⇾ X ⇾ X ⇾ X ⇾ …
Field fNext has incomplete type.
215
© Dr Markus Lumpe, 2021
Singly-Linked List (Node)
DataType is application-specific
We need to use pointers
• A list manages a collection of elements.
• The class SinglyLinkedList defines a value-based sequence container for values of type
DataType.
• To break infinite recursion, we have to use pointers to the next elements. This way, the compiler can deduce the size of a singly-linked list element and compile the definition.
216
© Dr Markus Lumpe, 2021
Singly-Linked List with R-Values
l-value constructor
r-value constructor
• The r-value constructor can “steal” the memory of the argument aData to initialize the payload fData. To use this constructor, the parameter aData must be a temporary of literal value. © Dr Markus Lumpe, 2021
217
A Simple List of Integers
define DataType a synonym for int
218
© Dr Markus Lumpe, 2021
Using Declaration — C++11 Type Aliases
• A type alias is a name that refers to a previously defined type.
using identifier = type;
• Type aliases are commonly used for three purposes:
• To hide the implementation of a given type.
• To streamline complex type definitions making them easier to understand, and
• To allow a single type to be used in different contexts under different names.
• Type aliases establish a nominal equivalence between types.
• Type aliases are similar to typedef. However, type aliases are
better suited when creating alias templates. 219
© Dr Markus Lumpe, 2021
Can we do better?
220
© Dr Markus Lumpe, 2021
Templates – C++’s Generic Types
• Templates are blueprints from which classes and/or functions are automatically generated by the compiler based on a set of parameters.
•Note, every time a given template is being instantiated with type parameters that have not been used before, a new version of the class or function is generated.
• A new version of a class or function is called specialization of the template. Specializations are not mutually compatible.
221
© Dr Markus Lumpe, 2021
Class Template
• A template is a parameterized abstraction over a class.
• From the language-theoretical perspective, templates are 2nd order
functions from types to classes/functions.
• To instantiate a class template we supply the desired types, as actual template parameters, so that the C++ compiler can synthesize
template
class AClassTemplate
{
// class specification
};
a specialized class for the template. 222
© Dr Markus Lumpe, 2021
Singly-Linked List Class Template
The typename parameter binds all occurrence of DataType in SinglyLinkedList
223
© Dr Markus Lumpe, 2021
The New Main
224
© Dr Markus Lumpe, 2021
We instantiate the template SinglyLinkedList to SinglyLinkedList
Class Template Instantiation
using IntegerList = SinglyLinkedList
using ListOfIntegerLists = SinglyLinkedList
• Types used as arguments cannot be classes with local scope.
• Once instantiated, a class template can be used as any other class.
225
© Dr Markus Lumpe, 2021
Using IntegerList Type Alias
type alias for SinglyLinkedList
226
© Dr Markus Lumpe, 2021
List Iterator Template
227
© Dr Markus Lumpe, 2021
SinglyLinkedList Iterator Specification
228
© Dr Markus Lumpe, 2021
We maintain a pointer to read-only list elements
Notes on Templates
• When using templates, the C++ compiler must have access not only the specification of a template class but also to all method implementations in order to properly instantiate the template.
• Templates are not to be confused with library classes. Templates are blueprint that have to be instantiated for each separate type application.
• Think of templates as special forms of macros.
• When defining a template class, we need to implement, like in Java, all methods within the class definition, usually in a header file.
229
© Dr Markus Lumpe, 2021
Templates have no .cpp file!
230
© Dr Markus Lumpe, 2021
Constructor & Deference
231
© Dr Markus Lumpe, 2021
For iterator implementation in header file.
Increments
232
© Dr Markus Lumpe, 2021
Equivalence
233
© Dr Markus Lumpe, 2021
Auxiliaries (For-Range)
234
© Dr Markus Lumpe, 2021
SinglyLinkedList Iterator Test
For iterator implementation see Canvas
235
© Dr Markus Lumpe, 2021
address of Three
SinglyLinkedList Iterator: Specification B
We maintain a read-only reference to list elements
236
© Dr Markus Lumpe, 2021
Reference Data Members
class ClassWithRefMember
{private:
SomeType& fRef;
Reference data members must be initialized before the contructor
body is entered!
public:
ClassWithRefMember( SomeType& aRef ) : fRef(aRef)
{ … } };
• Reference member variables store references to data outside an object. These references are established upon object creation via a member initializer.
• In case of iterators this might be an attractive option to avoid coping the underlying collection.
• Important: Reference data members require a constructor initializer.
237
© Dr Markus Lumpe, 2021
Constructor & Deference B
Establish reference
238
© Dr Markus Lumpe, 2021
fIndex is a pointer
Increments B
239
© Dr Markus Lumpe, 2021
unchanged
Equivalence B
compare addresses
240
© Dr Markus Lumpe, 2021
Auxiliaries (For-Range) B
241
© Dr Markus Lumpe, 2021
use address
SinglyLinkedList Iterator Test B
For iterator implementation see Canvas
242
© Dr Markus Lumpe, 2021
Three passed as l-value reference
Pointers
243
© Dr Markus Lumpe, 2021
The Need for Pointers
• A linked-list is a dynamic data structure with a varying number of nodes.
• Access to a linked-list is through a pointer variable in which the base type is the same as the node type:
IntegerList
IntegerList
244
© Dr Markus Lumpe, 2021
Node Construction
IntegerList *p, *q;
p = new IntegerList( 5 );
q = new IntegerList( 7, p );
p q
5
Nil
7
5
Nil
245
© Dr Markus Lumpe, 2021
Node Access
int a = p->fData;
int b = q->fNext->fData;
a: p
q
5
Nil
7
5
Nil
b:
246
© Dr Markus Lumpe, 2021
Inserting a Node
6
Nil
r
p q
r
IntegerList *r;
r = new IntegerList( 6 ); r->fNext = p;
q->fNext = r;
5
Nil
6
5
Nil
7
6
5
Nil
247
© Dr Markus Lumpe, 2021
Deleting a Node
q
q->fNext = q->fNext->fNext;
p
q
r
6
5
Nil
7
5
Nil
7
5
Nil
6
5
Nil
248
© Dr Markus Lumpe, 2021
Insert at the Top
IntegerList *p = nullptr;
p = new IntegerList( 5, p );
p
p = new IntegerList( 7, p ); p
5
Nil
7
5
Nil
249
© Dr Markus Lumpe, 2021
Insert at the End
• To insert a new node at the end of a linked list we need to search for the end:
250
© Dr Markus Lumpe, 2021
Insert at the End: The Pointers
7
5
Nil
p
*
*
9
Nil
pPtr
5
9
Nil
7
p
251
© Dr Markus Lumpe, 2021
Insert at the end preserves the order of list nodes.
252
© Dr Markus Lumpe, 2021
Insert at the End with Aliasing
• Rather than using a Pointer-to-Pointer we can just record the last next pointer.
253
© Dr Markus Lumpe, 2021
Complications with Singly-Linked Lists
• The deletion of a node at the end of a list requires a search from the top to find the new last node.
254
© Dr Markus Lumpe, 2021