Lecture Preview: Linked Lists

(Suggested book reading: Programming Abstractions in C++, 12.2 - 12.3; 14.3)

Today we will use pointers and nodes to make a collection called a linked list. A linked list implements the operations of a list or vector by storing a 'front' pointer to the first node in a chain of linked node values.

figure

To add or remove elements from a linked list, you must either modify its 'front' pointer, or modify the 'next' pointer of one of the existing nodes. For example, if you want to insert a new element at index 2, you must modify the 'next' pointer of the element in index 1, as shown in the figure below.

figure

Linked lists can be very tricky to master, so we'll practice them over several lectures.

This document and its content are copyright © Marty Stepp, 2018. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.