Data Structures  
Lecture 03: Linked Lists  
Edirlei Soares de Lima  
<edirlei.lima@universidadeeuropeia.pt>  
Dynamic Structures vs Arrays  
Array:  
Occupies a continuous space in memory;  
Allows random data access;  
Requires the predefinition of memory space needed;  
Dynamic Structure:  
Grow in size (or decrease) as elements are inserted (or removed);  
Examples: Linked lists, stacks, queues, trees, ...  
Linked Lists  
A Linked List is a sequence of elements, where each element  
has information stored and a pointer to the next element in  
the sequence:  
head  
.
. .  
DataN  
Data1  
Data2  
Data3  
Comprises a chained sequence of elements, called list nodes;  
Each node is composed of two properties:  
Stored data;  
A pointer to the next element of the list;  
The list is represented by a pointer to the first node;  
The pointer of the last element is null.  
Linked Lists Node Structure  
public class Node<T>  
{
private Node<T> next;  
private T data;  
.
..  
}
next  
next  
data  
data  
Linked Lists  
head  
.
. .  
DataN  
Data1  
Data2  
Data3  
Common operations in linked lists:  
Create;  
Insert;  
Print;  
Test empty;  
Search;  
Remove;  
Sort;  
Ordered insert;  
Compare;  
...  
Linked List Generic Class  
public class Node<T>{  
private Node<T> next;  
private T data;  
public Node(T t){  
next = null;  
data = t;  
}
public Node<T> Next{  
get { return next; }  
set { next = value; }  
}
public T Data{  
get { return data; }  
set { data = value; }  
}
}
public class LinkedList<T>{  
private Node<T> head;  
.
..  
}
Linked List Create  
O(1)  
public LinkedList()  
{
head = null;  
}
null  
Creates a new empty linked list by pointing the head to null  
Linked List Insert at the Beginning  
O(1)  
public void InsertAtBegin(T data)  
{
Node<T> node = new Node<T>(data);  
node.Next = head;  
head = node;  
}
new node  
1. Creates the new node;  
head  
data  
2. Inserts the new node in  
the beggining of the list;  
Data1  
Data2  
Data3  
Linked List Example  
LinkedList<int> myList = new LinkedList<int>();  
myList.InsertAtBegin(23);  
myList.InsertAtBegin(45);  
head  
head  
45  
23  
Linked List Traverse  
We can implement the GetEnumerator method in the generic  
class to allow us to iterate over the array using a foreach.  
public IEnumerator<T> GetEnumerator()  
O(n)  
{
Node<T> current = head;  
while (current != null)  
{
yield return current.Data;  
current = current.Next;  
}
}
head  
.
. .  
DataN  
Data1  
Data2  
Data3  
Linked List Print Example  
foreach (int i in myList)  
{
Debug.Log(i);  
}
Linked List Is Empty?  
public bool IsEmpty()  
O(1)  
{
if (head == null)  
return true;  
else  
return false;  
}
head  
.
. .  
DataN  
Data1  
Data2  
Data3  
Linked List Linear Search  
public Node<T> Search(T data){  
O(n)  
Node<T> current = head;  
while (current != null){  
if (current.Data.Equals(data)){  
return current;  
}
current = current.Next;  
}
return null;  
}
Node<int> node = myList.Search(42);  
if (node != null)  
Debug.Log("Element found: " + node.Data);  
else  
Debug.Log("Element not found!");  
Linked List Insert at the End  
Two cases:  
The new element will be the first element of the list;  
The new element is not the first element of the list.  
public void InsertAtEnd(T data){  
O(n)  
Node<T> node = new Node<T>(data);  
if (head == null){  
node.Next = head;  
head = node;  
}
else{  
Node<T> current = head;  
while (current.Next != null)  
current = current.Next;  
current.Next = node;  
}
}
Linked List Insert After  
public void InsertAfter(T after, T data)  
O(n)  
{
Node<T> afterNode = Search(after);  
if (afterNode != null)  
{
Node<T> newNode = new Node<T>(data);  
Node<T> temp = afterNode.Next;  
afterNode.Next = newNode;  
newNode.Next = temp;  
}
}
Linked List Remove  
Input: element to remove.  
If the element to be removed is the first element of the list,  
updates the head:  
head  
.
. .  
DataN  
Data1  
Data2  
Data3  
Otherwise, remove the element and update the next pointer:  
head  
.
. .  
DataN  
Data1  
Data2  
Data3  
Linked List Remove  
public void Remove(T data){  
O(n)  
Node<T> current = head;  
Node<T> previous = null;  
/
/search and keep both current and previous pointers  
while ((current != null) && (!current.Data.Equals(data)))  
{
previous = current;  
current = current.Next;  
}
if (current != null)  
{
if (previous == null) //remove from the beginning  
head = current.Next;  
else  
//remove from any other place  
previous.Next = current.Next;  
}
}
Linked List Insert in Order  
The insert function iterates over the elements of the list until  
it finds the correct position for inserting the new element:  
head  
.
. .  
DataN  
Data1  
Data2  
Data3  
New  
New  
Linked List Insert in Order  
public void InsertOrdered(T data){  
Node<T> newNode = new Node<T>(data);  
Node<T> current = head;  
Node<T> previous = null;  
while ((current != null) && //search the correct position  
(
current.Data.CompareTo(newNode.Data) < 0)){  
previous = current;  
current = current.Next;  
}
if (previous == null){ //insert in the beginning  
newNode.Next = head;  
head = newNode;  
}
else{  
newNode.Next = previous.Next;  
previous.Next = newNode;  
//insert in other places  
}
}
Linked List Insert in Order  
To compare data in a generic class using the CompareTo  
function, the class must IComparable interface:  
public class Node<T> where T: IComparable  
{
.
..  
}
public class LinkedList<T> where T : IComparable  
{
.
..  
}
Linked List Compare Lists  
public bool IsEqual(LinkedList<T> l)  
{
Node<T> current1 = head;  
Node<T> current2 = l.head;  
while ((current1 != null) && (current2 != null))  
{
if (current1.Data.CompareTo(current2.Data) != 0)  
return false;  
current1 = current1.Next;  
current2 = current2.Next;  
}
/
/check if both lists ended at the same time  
if ((current1 == null) && (current2 == null))  
return true;  
else  
return false;  
}
Doubly Linked Lists  
Each element has a pointer to the next element and a pointer  
to the previous element;  
Given an element, it is possible to access the next and the  
previous elements;  
Given a pointer to the last element of the list, it is possible to  
traverse over the list in reverse order;  
head  
Data1  
Data2  
Data3  
Doubly Linked Lists  
public class DoublyNode<T>{  
private DoublyNode<T> next;  
private DoublyNode<T> prev;  
private T data;  
.
..  
}
public class DoublyLinkedList<T>{  
private DoublyNode<T> head;  
private DoublyNode<T> tail;  
.
..  
}
head  
tail  
next  
next  
data  
data  
prev  
prev  
Doubly Linked List Insert at the  
Beginning  
public void InsertAtBegin(T data){  
DoublyNode<T> node = new DoublyNode<T>(data);  
node.Data = data;  
node.Next = head;  
node.Prev = null;  
if (head != null)  
head.Prev = node;  
head = node;  
if (tail == null)  
tail = node;  
}
New  
head  
Data1  
Data2  
Data3  
Applications in Game Programming  
Everywhere when dynamic set of objects is needed: list of  
enemies, list of waypoints, list of bullets, player inventory,  
game levels, layered tile maps, etc.  
Assignment Linked Lists  
1
) Implement a function to insert a new element at the end of a  
Doubly Linked List.  
head  
tail  
2
) Implement a function to insert a new element after an existing  
element of a Doubly Linked List.  
tail  
head  
Further Reading  
Penton, R. (2002). Data Structures for Game Programmers.  
Muska & Lipman/Premier-Trade. ISBN: 978-1931841948  
Chapter 6: Linked Lists  
Sherrod, A. (2007). Data Structures and Algorithms for  
Game Developers. Charles River Media. ISBN: 978-  
1
584504955  
Chapter 5: Link Lists