Notice that each node in the list contains two attributes, the value stored at that node and a reference to the node after it.
The same sequence of data, stored in linked together nodes (a linked list), would look like this: In an array, those values would be stored contiguously in memory as in this illustration: Suppose we have a sequence of integers 3, 8, -6, 0, 12, -1, -4, 9. What if the cells weren't contiguous? What if instead they were scattered throughout memory and connected together like a chain? We call such a structure a linked list, and it is the focus of the rest of this module. There isn't much we can do about the cost of locating the zero, but once we do locate it, we can make the insertion itself constant time. The performance problem with inserting values in arrays comes from the contiguous allocation of cells and therefore the need to shift values out of the way. Inserting After a Known Value In an Array Video Example Introducing the Linked List As you review this, imagine that the array is much longer to visualize the performance problem. To see this in a more practical (and small) case, consider the next video, where we implement a function to insert a value after the first zero in an array. This is \(O(n)\) time because in the worst case we insert at position zero and every existing cell must be moved. Now imagine that the red section is very large-billions of elements. In the image below, we insert a value at the yellow cell, requiring all of the subsequent red cells to shift right. Because the cells are contiguous, we must shift everything after the point of insertion to the right to make room. Suppose we have a huge array of data and we want to insert something at or near the beginning. The same contiguous allocation that gives arrays fast access times also gives them slow insertion/removal time. If an application needs to insert or remove several values, arrays are not the best choice.
This means that applications requiring lots of accesses to existing data will benefit from using arrays because those accesses are constant-time. Adding the index to the base address of the array to find the location of a cell is a constant-time operation implemented in the computer's processor hardware. The beauty of arrays is that their contiguous allocation in memory gives us constant time access to any known location. Slides (part 2) used for in-class session (PPTX) When Arrays are Good and Bad Slides (part 1) used for in-class session (PPTX) Project 2: Literally Loving Linked Lists LOL DUE Tuesday, 26 October 2021 2359 EDT CSCI 241 Section 1.3: Multidimensional Arrays