Linked lists

Using arrays to store very dynamic lists, as in the example on Tuesday, is very inefficient

Creating and deleting the arrays often

Copying whole arrays just to add or delete an element

A linked list consists of a collection of nodes

Each node contains

One data element of the list

A pointer to the next node in the list, called a link

To use a linked list, we need

A pointer to the first element of the list

A pointer to the last element of the list (for efficiency)

A method to create new elements containing our data

A method to remove elements from the list

Methods to manipulate the list (sort, search, etc.)

Some number of elements in the list

Picture:

Conceptual

In memory

Example:

Adding an element to an array that is big enough to handle another element

Adding an element to an array that isn't big enough

With linked lists:

Finding an element in a list

Adding an element to a linked list

Deleting an element from a list

Implementing linked lists

Two useful classes:

Listnode - containing data and next

Linkedlist - containing first and last elements, and data manipulation functions.

Stacks

A stack is a data structure that works like a pile of objects.

When objects are added to a stack, they are put on top.

When objects are removed from a stack, they are taken from the top

A stack is a last-in-first-out (LIFO) data structure.

How would we implement a stack using a linked list?

What kinds of problems would a stack be useful for?

Queues

A queue is a data structure that works like a line of people waiting to buy student tickets to a football game.

When objects are added to a queue, they are put on at the back of the queue.

When objects are removed from a queue, they are taken from the front

A queue is a first-in-first-out (FIFO) data structure.

How would we implement a queue using a linked list?

What kinds of problems would a queue be useful for?