Arrays, Linked Lists & Queues

Arrays

Arrays are data structures which are of a fixed size and contain data of the same type stored in a contiguous block of memory.

1D array

A 1-dimensional array is a single set of data, which can be visualised in a single row. - For example: oneDArray = [A, B, C, D]

2D array

A 2-dimensional array is a set of data which can be visualised in rows and columns.
For example, array twoDArray = [[A, B, C, D], [E, F, G, H],[I, J, K, L]]
Items in a 2-dimensional array are referred to by their row number, followed by column number.
For example, twoDArray [1,2] = G

3D array

A 3-dimensional array is a collection of 2-dimensional arrays.
You can visualise each 2D array as being stored one behind the other.
- For example, threeDArray = [[[A, B, C, D], [E, F, G, H],[I, J, K, L]], [[M, N, O, P], [Q, R, S, T],[U, V, W, X]],[[Y, Z, 0, 1], [2, 3, 4, 5], [6, 7, 8, 9]]]

3D array cont.

Items in a 3-dimensional array are referred to by their 2D array number, followed by the row number, and column number.
- For example, threeDArray [1,2,2] = W

Linked List

Linked lists are commonly used data structures with benefits of flexibility and ease of use. They can be used to implement other data structures such as stacks and queues.

Linked list

Linked lists consist of nodes.
Each node contains a data item and a pointer to the next node in the sequence.
A null pointer is used to identify the last item of data.
The use of pointers means that unlike arrays, data in linked lists do not have to be stored contiguously in memory.
They are also referred to as being ‘dynamic’ in that they can grow or shrink in size as and when necessary.

Example

The diagram shown is graphical representation of a linked list containing the names of three animals in alphabetical order.

Adding nodes

To add ‘Tiger’ to the list alphabetically, the pointer of node 1 is updated to point to the new node, which in turn points to the next in the sequence (node 2).

Deleting nodes

To delete ‘Rhino’ from the list, the pointer of node 0 is updated to point to node 3.
The data of node 1 is deleted.
This node becomes the first of a separate list of empty nodes, ready to be filled again.

Queues

A queue is a data structure where data items are always added to the end and removed from the front. It is often referred to as a 'first in, first out’ data structure.

Queues

Queues can be implemented using other data structures, such as arrays or linked lists.
In either case, two extra variables are required to identify the front and rear of the queue.
Queues can be ‘static’ (fixed in size) or ‘dynamic’ (able to grow in size as necessary)

Queue operations

Several operations can be carried out on queues:
- enQueue() - adds an item to the rear of a queue.
- deQueue() - removes and displays the item at the front of a queue.
- isEmpty() - checks to see if the queue is empty.
- isFull() - checks to see if the queue is full.

Uses

Queues have a wide range of uses in computer science, including:
- Storing print jobs until the printer is ready to print.
- CPU scheduling.
- Breadth-first traversal of a graph.

Linear or circular

Queues can also be ‘linear’ or ‘circular’.
When an item of data is removed from the front of a linear queue, all the other items move up one place.
- This is only suitable in a small queue, otherwise data processing time can be excessive.
When an item of data is removed from the front of a circular queue, the only processing required is to update the two pointers identifying the new front and rear of the queue.

1Components of a Computer

1.1Structure & Function of the Processor

1.1.1Structure of the CPU

1.1.2Fetch, Decode, Execute Cycle

1.1.3Factors Affecting CPU Performance

1.1.4CPU Architecture

1.2Types of Processors

1.2.1CISC & RISC

1.2.2Multicore & Parallel Cores

1.3Input, Output & Storage

1.3.1Computer Systems

1.3.2Magnetic Storage

1.3.3Optical Storage

1.3.4Types of Optical Storage

1.3.5Types of Memory

1.3.6Flash Memory

1.3.7Virtual Memory

2Software & Software Development

3Exchanging Data

4Data Types, Data Structures & Algorithms

4.1Data Types

4.1.1Data Types

4.1.2Arrays & Strings

4.1.3Representing Numbers

4.1.4Binary Arithmetic

4.1.5Hexadecimal

4.1.6Converting Binary Numbers

4.1.7Floating Points in Binary

4.1.8Floating Point Arithmetic

4.1.9Bitwise Manipulation

4.1.10Character Sets

4.2Data Structures

4.2.1Arrays, Linked Lists & Queues

4.2.2Graphs, Hash Tables & Stacks

4.2.3Trees

4.3Boolean Algebra

4.3.1Computational Logic

4.3.2Boolean Logic

4.3.3Karnaugh Maps

4.3.4Boolean Identities

4.3.5Flip Flops & Adder Circuits

5Legal, Moral, Cultural & Ethical Issues

5.1Computing Related Legislation

5.1.1Data Protection Act (1998)

5.1.2Computer Misuse Act (1990)

5.1.3Copyright Designs and Patents Act (1988)

5.1.4Regulation of Investigatory Powers Act (2000)

5.2Moral & Ethical Issues

5.2.1Online Activity Tracking

5.2.2Censorship

5.2.3Cultural Issues

5.2.4Environmental Issues

5.2.5Layout, Colour Paradigms & Character Sets

6Elements of Computational Thinking

6.1Thinking Abstractly

6.1.1Abstraction

6.2Thinking Procedurally

6.2.1Decomposition

6.3Thinking Logically

6.3.1Pseudocode & Flow Diagrams

7Problem Solving & Programming

7.1Programming Techniques

7.1.1Programming Fundamentals

7.1.2Modularity

7.2Programming Construction

7.2.1Integrated Development Environments

7.2.2Testing

8Algorithms

8.1Algorithms

8.1.1Interpreting, Correcting & Completing Algorithm

8.1.2Sort Algorithms

8.1.3Insertion & Merge Sort

8.1.4Search Algorithms

Jump to other topics