1 of 10

1.4 Data Types, Data Structures and Boolean Algebra

1.4.1 – Data Structures

​

Linked Lists

2 of 10

Learning Objectives

  • I am familiar with the concept of a abstract data structures and can utilise and implement lists and linked lists

Explore -   I show a good understanding of the above data structures

(Grade U to D)

Enhance - I show a good understanding of the above data structures and can write pseudocode algorithms to meet requirements with a queue. (Grade C to B)

Excel - I evidence a clear understanding of the above data structures and can implement a linked list.

(Grade A* to B)

3 of 10

List

  • A dynamic data structure

​

  • Items can be repeated, changed and the list can change in size.

4 of 10

Adding to a list

Bill

Emily

Sarah

Ken

Hayley

​

Bill

Emily

​

​

Sarah

Ken

​

Hayley

​

Items are moved up in the array to make space for new item

Bill

Emily

​

Daniel

Sarah

Ken

​

Hayley

​

New item is inserted.

Deleting items is the same process in reverse. Item is deleted and other items moved to fill the gap

5 of 10

Linked Lists

  • A dynamic data structure used to hold a sequence

​

    • The items in the data structure are not necessarily held in contiguous data locations (they are not necessarily held in their actual sequence)

​

    • Each data field has an associated pointer, which references that items location in the sequence.

​

    • The pointer holds the address of the next item in the sequence

6 of 10

Linked Lists

  • To implement a linked list – first an array must be initialised.

​

Array Index

Name

Pointer

0

​

1

1

​

2

2

​

3

3

​

4

4

​

5

5

​

null

start = null

​

nextFree = 0

A pointer named start is set to null – to show that the list is empty. When the list is populated with data, the start variable will change to 0.

​

The nextFree variable is set to 0 to state that the next available array index is 0.

7 of 10

Linked Lists

  • After the list is populated….

​

start = 0

​

nextFree = 4

The start pointer points to 0 – the first item in the list.

​

The nextFree variable is set to 0 to state that the next available array index is 0.

Array Index

Name

Pointer

0

Browning

3

1

Turner

null

2

Johnson

1

3

Cray

2

4

​

5

5

​

null

8 of 10

Inserting an item

Array Index

Name

Pointer

0

Browning

3

1

Turner

null

2

Johnson

4

3

Cray

2

4

Mortimer

1

5

​

null

  • Store the new name Mortimer in the node pointed to by nextFree
  • Determine, by following links, where new item should be linked in
  • Change next free to point to the next free location
  • Change Mortimer’s pointer to point to Turner
  • Change Johnson’s pointer to point to Mortimer

start = 0

​

nextFree = 5

9 of 10

Pseudocode

  • Names[p].name = holds the name in node[p]

​

  • Names[p].pointer = holds the value of the pointer in node[p]

10 of 10

Pseudocode

newName = input(“Enter name”)

Names[nextfree].name = newName

P = start

#follow pointers until names[p].pointer

#points to a name that is > new name

Temp = nextfree

Nextfree = Names[temp].pointer

Names[temp].pointer = Names[p].pointer

Names[p].pointer = temp