Lists and Pointers

Lists and Pointers

Quote to remember

“A list is only as strong as its weakest link”

-Don Knuth

Abstract data types

It doesn’t matter what programming language you are using. A programming language has to be able to distinguish between different types of data,

Some types of data include:

• Integer
• Double
• String
• Real

High level programming language also offers arrays and records which are data structures. Object oriented programming allows the declaration of classes, data structure combined with the methods that act on them.

Real-life problems often refer to structures, or containers, to store data items or objects, also called elements. Lists are examples of those structures We write shipping lists, to-do lists, and we can set-up our own play list.

Things that can happen in a play list:

• Elements can be added or deleted
• A list can grow or shrink
• This is known as dynamic structure
• A collection of elements within an inherent order

Viewing the list as an abstract data type

As a type who’s properties are specified independently of any particular programming language.

The operations that need to be performed on a list:

• Initialise lists (i.e. start a new list)
• Insert an element
• Find an element
• Delete an element
• Get length of list
• Output entire list

A linear lists stores its elements in adjacent locations. Elements in an array are stored physically in adjacent locations in main memory. When an array is declared, the compiler reserves the space for the array elements. This means that the arrays is a static structure.

A one-dimensional array can be used to store the elements of a list. The arrays however will need to declared with enough location to store the maximum number of elements the list may contain at any one time.

This is an example of an array. We allocate a block of memory and get it to behave like a list. The numbers stratin from 0x1000 are known as memory locations. The values to the right are known as data. This is what is stored at each memory location.

Array above is:

Storing 51 string

This is in continuous memory

How list operations be implemented?

-Initialisation of list: declaration of the array and initialising a variable numberofelements

-Insertion of an element: store the element in the next available space; increment the variable numberofelements

-Search for an element, p.g. 91

Deleting an element: find the element to be deleted and move subsequent elements up on space; decrement the variable.

Get the length of the list: this is the variable numberofelements

Output the entire list: start with the beginning and out element in turn until the last element is reached.

Advantages:

It is easy to program

If elements are stored in key order, a binary search can be performed

Disadvantage:

Memory locations maybe wasted due to array being static

Insertion of an element within an ordered list requires moving elements

Deletion of an element within a list requires moving elements

Main problems with Array

Imagine we have ball and we wanted to insert this into our array. The only problem is that our array needs to be in an ordered list. This will cause problems because ball will need to go between apple and cherry. This means that everything from cherry downwards have to be shifted down. This can be time consuming and taxing on resources.

Each time we insert an item we would need to the above operation. Can you imagine the slowness….

If you noticed, the array has a number i.e. 50, that means it is fixed. This cannot shrink or expand. If you want to add additional items, well, tough. This is where some people try to make an array really large but the problem with this is that usually memory is wasted as it is not properly utilised.

Linked list

The example above shows a linked list.

We have two parts:

Info: this is the data that we are going to store.

Next: this is the next memory location that will point to the next pointer. This may also point to a special pointer.

How is the linked list constructed:

-You start with 1 node

-When a new node is created, you simply update the reference part, which is labelled next to point to the next.

The extra bit that is added is the pointer.

You now have a list of two. When a third element comes along, you must update the reference point of the second node to point to the next reference point (node).

How do we know where a list begins and ends?

We use a special value called null, the null determines the start and end.

The reference part of the last node always points to the null.

To determine where the list starts

There is an external reference to the beginning of the list. This is known as the head. This will always point to the first node on the list.

Start > First node

Let’s see how this will solve the problems

Add a new element to a link list.

Let’s imagine that we want to add cat. The cat must be insert between banana and dog if we have sorted this alphabetically.

This is what we do:

-The first step is to get ourselves a pointer so we can traverse the list

-A pointer is just a thing that points to a node, nothing complicated

-The pointer can be called for example p

We can say that p will need to equal to the head, which is the starting point.

-Next, we can move the p along by using the next field

-Until we get to the node holding banana

-When we get here, we must do two things

-The next pointer of cat must point to the pointer of the dog

-The next pointer of the banana must point to the cat

-The order of this is really important: if you change the next pointer of banana, before updating the next pointer of the cat, you have lost the reference to dog

This means you have broken down the list.

Next, deleting a node

Deleting cat

-First we must get the pointer to move immediately before the node cat, which will be banana

-Next we will get banana to point to dog instead of cat

-We use the next field address of cat to get the dog address, then we update the address of banana to point to this address

-Cat will now have nothing pointed to it

p.next = p.next.next;

Caution

-Have null checks in place

-Make sure there isn’t any memory leackage

-

More notes

If we know the maximum number of elements, we can declare it:

Data [100]

If we don’t know, we can use dynamic structure.

A node will have two part.

One part data, the other part will store the next data. If there is no data, it will be null or 0.

If there is another node, then the next bit will have that address.

Which will be another box that will have the value null at the end.

You can always change the reference to point backwards as well. It all depends on the order in which the data is stored and needs to be stored in.

Start Head > Normal nodes.

Notes

It is called a linked list because the elements are linked by a set of pointers. Linked list structure.

What is it?

A linked list is a sequence of nodes i.e. nodes that are connected together. Each node has a reference i.e. link which will tell it where the next node is.

If you look at the example above we have two things:

Info: the info will be the data that it is going to store

Next : this is where the next item is going to be, i.e. the next node link (known as reference)

The Info can be string, integer or object.

Imagine list elements stored wherever there is a space ad linked to form a sequence. Each element of the list, known as a node, can be represented as a record of data fields, with an extra field used as a pointer that links a node to the next node in the list. A special pointer at the start, known as the start pointer, points the first node of the list. The last node in the list has a null pointer in the pointer field.

Pointer: a variable that contains an address. The pointer points to the memory location with that address.

Null pointer: a pointer that does not point to anything, usually represented by 0 or 1.

Advantages

The concept of linked list makes insertion and deletion element much less time consuming

Only the pointer fields are changed . To insert a new node at the beginning of the list, the content of the start variable is copied into the new node’s pointer field, then start variable is set to point to the new node,

Example is showing Ben being taken off and Fred being put on.

To insert a new node between Fred and Jack, the pointer field of the node for Fred is copied to the pointer field of the new node. The pointer field of the node for Fred is changed to point to the new node.

Node added to the end of the list:

The pointer field for the node for Jack, is changed to the new node. The pointer field of the node for matt is copied to the pointer field of the new node.

To delete fred, the pointer field for fred is copied over to jack.

If the last one is to be delete, the pointer field for the last one is copied across to the second last pointer.

How can we program such a linked list?

These linked lists can be sorted in an array, just as before, but instead of moving nodes to insert or delete elements, the nodes are connected via the pointers and the pointer values are the index of the array location of the node.

To insert a new node for Greg, only the pointers are adjusted.

To delete the node for Jack, only the pointers are adjusted.

But how can the now redundant node in array element 2 be reused? A second list can be produced by linking all free nodes together.

Page 90 how to add.

--- online tutorial

Linked list

What is a list?

-A list is a number of connected items or names written or printed consecutively

Examples (Non-computing):

-A to-do list

-A shopping list

-An order list

-A birthday list

-An invitation list

What is a list in computing?

-A list is best described by its properties and behaviour. It is an ordered collection of values (i.e. items, entries, elements)

-A value may occurs once

Things to remember:

-Ordered collection means: the order in which you put the list in is very important

-ABC, CBA are different things, so is 1,2,3 and 3,2,1

-A value may occur more than once which means that duplicated values are allowed

The above are the two things that distinguish a list from a set.

List is an ordered sequence of elements whereas Set is a distinct list of elements which is unordered (thank you, Quinn Taylor).

List<E>:

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

Set<E>:

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

Sets, by definition has no ordering.

Ordered list examples:

Linked list

Array list

Lists of unique elements conform to java’s interface named set, cannot be accessed by index:

Set<E>:

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

Summary:

A set cannot contain duplicated values while a list can.

Continuing:

What does a list do?

At a minimum it must:

-Add an element

-Remove an element

-Find an element

In addition, other things like concatenating two lists, add a bunch of items at once etc…

Linked lists

How are they implemented on a computer?

-Arrays

-Linked list

Arrays

Arrays are very easy to implement, you can do so in any programming language.

String [] a = new String[10]

You do the following:

-You allocate a block of memory

-You make that block of memory behave like a list

Example of an array with memory locations and the string that is being stored:

The example shows the arrays 10, which means 10 items will be stored in this array. This will be stored in contiguous memory.

So, now you might be asking why have linked lists at all? That looks perfectly fine right?

The problem with simple arrays is the following:

Inserting an item at a specific location in an array

-This becomes a problem because, in the example we have the items alphabetically sorted

-If we want to enter something new such as “Chocolate” this has to be insert after “B – Banana” and before “D – Dog”

This means that all the items from Dog onwards has to be shifted down by one, this is an expensive operation which can use resources, if you using this to insert an item.

Second disadvantage with array

-The size of the array is fixed when you create it

-If the array is full and a new element is to be added, it cannot be, due to the array being full

-You can also do the opposite, this is where you have an array, and you give too much space and utilise too little

This is where linked list comes

What is a linked list?

A linked list is a sequence of nodes. Each nodes contains a reference or a link to the next node on the list.

Every element on the list is called a node, each node has two parts:

One part contains data, the other part contains the reference.

Apple: this is the info

0x1001: this is the next node address (link)

The data part info could be anything. It could be a string, object, integer etc…

Next: this is the reference part. This contains some memory address. This memory address is linking to the next node on the list.

Resources:

Order collection