CMPS 260: Data Structures

Introduction

Linked lists are a little different compared to all the previous data structures we have seen. Instead of storing all elements in one place, we use nodes that store elements and the nodes are then linked together. The idea is that you keep a reference to the first node, and the first node references the second node, and the second node references the third node, and so on. Each node stores exactly one element. This implies that if you want to retrieve the tenth element, you have to go through the list all the way from the beginning, which is slower than using an array. However, inserting an element in the first location is faster than an array, because no elements have to be shifted. If this all sounds a bit abstract, think of a train where all the cars are linked together. If you want to get from the locomotive to the last car you have to step through all the ones in between. There are variations on a linked list that we will look at, such as doubly linked lists and circular linked lists.

Module Objectives

• Describe the linked list data structure
• Implement creating and using a linked list
• Implement creating and using a doubly linked lists
• Implement creating and using a circular linked lists

Learning Resources

• Module 5 Readings: Chapter 5 (skip ECMAScript sections)
• Module 5 Slides: Chapter 5

Learning Activities

• Module 5 Assignment

For Further Study

• Read more about linked lists on Wikipedia