top of page
This site was designed with the
.com
website builder. Create your website today.Start Now

Arrays, Lists, Stacks and Queues

Tutoring > Data Structures > Arrays, Lists, Stacks and Queues

Data can be stored in structures to keep it together and more easily accessible. Here are some of the simpler implementations of data structures commonly used ti store data.

Arrays

An array is an arrangement of items at equally spaced addresses in computer memory. The items are of the same type and each element takes up the same amount of memory.

An integer array is a collection of integers, a String array is a collection of Strings. The elements are indexed starting at 0. So the third index of an array has the index 2.

Stacks

A stack is a LIFO structure (Last in, First out). The size of a stack is the number of elements in it.

 

The operations for a list are:

  • Pop - Remove the top element from the stack, decreasing the size by 1.

  • Push - Add an element to the top of the stack, inreasing the size by 1.

  • Peek - Observes the top-most element without removing it.

 

Stacks are, on an abstract level, equivalent to linked lists.

 

A great analogy for a stack is as pez dispener. You can pop items from the top, or push items on to the top, but you can't access anything that isn't at the top. 

Lists

A list is a finite ordered collection of data types where the same value can occur more than once (Lists allow duplicate values).

So {1,1,1} is a List

So is {1}

and {1,2,3,4}

but {1,3,2} is not in order so is a Set.

The empty List {} is still a list.

 

Operations for a list include:

  • an operation for testing whether or not a list is empty

  • an operation for prepending an entity to a list

  • an operation for appending an entity to a list

  • an operation for determining the first component (or the "head") of a list

  • an operation for referring to the list consisting of all the components of a list except for its first (this is called the "tail" of the list.)

 

Linked lists can be represented like this :

 

 

 

 

 

 

 

 

 

The start shows a head pointer or header. Not all representations have this, some just start with the first element. Each cell then contains a value and a pointer to the next cell. A pointer is like a signpost to an address in memory, it directs you to exactly the thing it points to.

At the end is a terminator, This is just a NULL value and signifies the end of the list.

You can have singly linked lists or doubly linked lists, which have pointers to the last cell as well as the next.

 

Advantages of linked lists 

  • They are dynamic, allocating memory when it is required.

  • Insertion and deletion are implemented easily.

  • As they are not a fixed length, memory is not wasted

 

Disadvantages of linked lists

  • The pointers do take up memory space that other data structures would not (arrays for example).

  • Nodes are stored incontiguously (not next to each other in memory), this can greatly increase the time it takes to find a single node.

  • It's difficult to traverse a singly linked list backwards, where a doubly linked list has more pointers taking up memory.

Queues

A queue is much like a stack, but items are enqueued onto the back and dequeued from the front. This is a FIFO (First in, First out) structure.

The size of a queue is the number of elements in it. The operations for a queue are:

  • Enqueue - Add an element to the front of the queue, increasing the size by 1.

  • Dequeue - Remove an element from the back of the queue, decreasing the size by 1.

  • Peek - Observe the front element without removing it.

bottom of page