ECE250 Lecture Notes - Lecture 5: Linked List

• School: University of Waterloo
• Department: Electrical and Computer Engineering
• Course: ECE250
• Professor: Douglas Harder

Document Summary

Data structures and algorithms: data can be stored on a computer in one of three means: contiguous, linked, or indexed, contiguous allocations. Allocate a block of memory in an unbroken sequence. An example is the array: an array containing n elements occupies some multiple of n bytes in memory and that the memory is allocated in a single block. Issue: if more memory is required, it is the os that performs memory allocations. In most cases, after the array has been allocated in memory, other data is stored immediately after it, hence the array can"t be expanded. The os would usually allocate a larger array, copy all the data over to the new array, then the old array is de-allocated: linked allocation. Has each item stored together with a reference to the successor or related data. An example is a linked list: each object stores data, but also has a reference to the next object connected to it.