Data Structures - Linked Lists

Data Structures

Lecture 04: 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;

.

..

}

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

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

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

data

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