Creating linked list data structure

Overview

The purpose of this assignment is for you to write a data structure called a Linked List, which utilizes templates (similar to Javas generics), in order to store any type of data. In addition, the nature of a Linked List will give you some experience dealing with non-contiguous memory organization. This will also give you more experience using pointers and memory management. Pointers, memory allocation, and understand how data is stored in memory will serve you well in a variety of situations, not just for an assignment like this.

Background

Remember Memory?

Variables, functions, pointerseverything takes up SOME space in memory. Sometimes that memory is occupied for only a short duration (a temporary variable in a function), sometimes that memory is allocated at the start of a program and hangs around for the lifetime of that program. Visualizing memory can be difficult sometimes, but very helpful. You may see diagrams of memory like this:

x

y

Car

r

g

b

a

Other Memory

intx, y, z;

Vehiclecar;

charr, g, b, a;

Vehicle*ptr = &car;

z

ptr

Or, you may see diagrams like these:

0x665418b0

0x665418b4

0x665418b8

0x665418bc

0x665418c0

0x665418c4

0x665418c8

0x665418cc

0x665418d0

x

y

z

Car

r

intx, y, z;

intx, y, z;

If you are trying to draw out some representation of memory to help you solve a problem, any of these (or some alternative that makes sense to you) will be fine. COP3503 Programming Fundamentals 2

Arrays

Arrays are stored in what is called contiguous memory. A contiguous memory block is one that is not interrupted by anything else (i.e. any other memory block). So if you created an array of 5 integers, each of those integers would be located one after the other in memory, with nothing else occupying memory between them. This is true for all arrays, of any data type.

2

4

6

8

10

Other Memory

Other Memory

someArray

intsomeArray[5];

someArray[0] = 2;

someArray[1] = 4;

someArray[2] = 6;

someArray[3] = 8;

someArray[4] = 10;

All of the data in an application is not guaranteed to be contiguous, nor does it need to be. Arrays are typically the simplest and fastest way to store data, but they have a grand total of zero features. You allocate one contiguous block, but you cant resize it, removing elements is a pain (and slow), etc.

Consider the previous array. What if you wanted to add another element to that block of memory? If the surrounding memory is occupied, you cant simply overwrite that with your new data element and expect good results.

2

4

6

8

10

Someone elses memory

Other Memory

someArray[5] = 12; // #badIdea

This will almost certainly break.

In this scenario, in order to store one more element you would have to:

1. Create another array that was large enough to store all of the old elements plus the new one

2. Copy over all of the data elements one at a time (including the new element, at the end)

3. Free up the old arrayno point in having two copies of the data

Old Array

2

4

6

8

10

Someone elses memory

Other Memory

--

--

--

--

--

--

Create New Array

Uninitialized values

2

4

6

8

10

Someone elses memory

Other Memory

2

4

12

Copy old data to the new array

And thenew guy

Someone elses memory

Other Memory

2

4

6

8

10

12

Newly available memory

Lastly, delete the old array

This process has to be repeated each time you want to add to the array (either at the end, or insert in the middle), or remove anything from the array. It can quite costly, in terms of performance, to delete/rebuild an entire array every time you want to make a single change. Cue the Linked List! COP3503 Programming Fundamentals 2

Linked List

The basic concept behind a Linked List is simple:

1. Its a container that stores its elements in a non-contiguous fashion

2. Each element knows about the location of the element which comes after it (and possibly before, more on that later)

So instead of a contiguous array, where element 4 comes after element 3, which comes after element 2, etc you might have something like this:

First

Second

Third

Fourth

Null

Each element in the Linked List (typically referred to as a node) stores some data, plus some sort of reference (a pointer, in C++) to whatever node should come next. The First node knows only about itself, and the Second node. The Second node knows only about itself, and the Third, etc. In this example the Fourth node has a null pointer as its next node, indicating that weve reached the end of the data.

A real-world example can be helpful as well:

Think about a line of people, with one person at the front of the line. That person might know about the person who is next in line, but no further than that (beyond him or herself, the person at the front doesnt need to know or care). The second person in line might know about the third person in line, but no further. Continuing on this way, the last person in line knows that there is no one else that follows, so that must be the end. Since no one is behind that person, they must be at the end of the line.

First In Line

etc

Next == null, must be at the end

So What are the advantages of storing data like this? When inserting or removing elements into an array, the entire array has to be reallocated. With a Linked List, only a small number of elements are affected. Only elements surrounding the changed element need to be updated, and all other elements can remain unaffected. This makes the Linked List much more efficient when it comes to adding or removing elements.

Now, imagine one person wants to step out of line. If this were an array, all of the data would have to be reconstructed elsewhere. In a Linked List, only three nodes are affected: 1) The person leaving, 2) the person in front of that person, and 3) the person behind that person.

Imagine you are the person at the front of the line. You dont really need to know or care what happens 10 people behind you, as that has no impact on you whatsoever. COP3503 Programming Fundamentals 2

First

Leaver

If the 5th person in line leaves, the only parts of the line that should be impacted are the 4th, 5th, and 6th spaces.

1. Person 4 has a new next Person: whomever was behind the person behind them (Person 6).

2. Person 5 has to be removed from the list.

3. Person 6 actually does nothing. In this example, a Person only cares about whomever comes after them. Since Person 5 was before Person 6, Person 6 is unaffected. (A Linked List could be implemented with two-way information between nodesmore on that later).

The same thought-process can be applied if someone stepped into line (maybe a friend was holding their place):

First

New Guy

In this case, Person 2 would change their next person from Person 3, to the new Person being added. New Guy would have his next pointer set to whomever Person 2 was previously keeping track of, Person 3. Because of the ordering process, Person 3 would remain unchanged, as would anyone else in the list (aside from being a bit irritated at the New Guy for cutting in line).

So thats the concept behind a Linked List. A series of nodes which are connected via pointer to one another, and inserting/deleting nodes is a faster process than deleting and reconstructing the entire collection of data. Now, how to go about creating that?

Terminology Node	The fundamental building block of a Linked List. A node contains the data actually being stored in the list, as well as 1 or more pointers to other nodes. This is typically implemented as a nested class (see below).
Singly-linked	A Linked List would be singly-linked if each node only has a single pointer to another node, typically a next pointer. This only allows for uni-directional traversal of the datafrom beginning to end.
Doubly-linked	Each node contains 2 pointers: a next pointer and a previous pointer. This allows for bi-directional traversal of the dataeither from front-to-back or back-to-front.
Head	A pointer to the first node in the list, akin to index 0 of an array.
Tail	A pointer to the last node in the list. May or may not be used, depending on the implementation of the list.