CSE 116 Lecture Notes - Lecture 4: Array Data Structure, Linked List, Data Element
Document Summary
Cse 116 intro to computer science ii. This lab will use the concept of a doubly-linked list to provide the capability for a more flexible array structure. The traditional array while being very efficient as regards execution time is relatively inflexible. It is a modern programming language implementation of a block of memory, accessed as a fixed number of data elements. Good points: no meta-data in memory (no wasted memory, random access with a simple calculation, access to known index in constant time. Bad points: number of elements is fixed (cannot be expanded dynamically, each element"s location in the array is fixed (no insertions) In order to make a better array we will add meta-data in memory (bad) and give up the ability to access a known index in constant time (bad). However, we will gain the ability to extend the array indefinitely (good) and to insert or delete an element anywhere in the array (good).