Linked Lists

• Given an ordered-list: – What happens when we add an element to the list? – What happens when we delete an element from the list? • In the array implementation, such cases require heavy data movement which is very costly. • When we deal with linear or ordered-lists, it is in general not required to have a random access to the elements. e.g., we usually don’t need to ask questions like: what is the 8th element in the list? • In most cases, the data is processed in a strictly sequential order. • Therefore all that is required is the access to next element.

• In our previous mapping, the next element happens to be the elemental at the next index in the array. • If we can some how tell where the next element is stored, we can eliminate this restriction of placing the next element at the next physical location! • This gives rise to the nation of logical adjacency as opposed to physical adjacency.

• In that case, in order to access the elements of the list, all we need is a starting point and some mechanism to from one element to the next. • In other words, we need a starting point and a link from one element to the next.

Treasure Hunt for Kids • In a party, clues are made up and scattered all over the house. Kids are divided into teams of 1 to 4, depending on how many are at the party. Each clue leads to the next and at the end of the trail is a treasure for the team, for example, chocolates, toys, etc.

• In that case, in order to access the elements of the list, all we need is a starting point and some mechanism to from one element to the next. • In other words, we need a starting point and a link from one element to the next. • We can only travel in the direction of the link. • We have a chain like structure and we can access the elements in the chain by just following the links in the chain. • Such an organization is known as a linked-

Linked-lists • This organization rids us from the requirement to maintaining the logical as well as physical adjacency. • Now all we need to maintain is the logical sequences and two logically adjacent elements need to not be physically next to each other.

Linked-lists • We can implement this organization by storing the information and handle to the next element with the other data as follows:  struct element { handle next; // handle to next list element data_type data; };   handle head; // starting point - handle to first list element head = φ // initialize head to φ - the end marker

Linked-lists • A list node and the resulting list looks like as shown below:

Data

Head

2

5

Next

8

10

15

∅

Linked-lists – Traversal void traverse (handle head) { handle current = head; while ( current != φ ) { process data at current; current = next field of current element } } Head 2 5 8 10 15 curren t

∅

Linked-List Add an Element after current element void add (handle current, data_type data) { handle new_element; new_element = get a new element; data field of new_element = data; next field of new element = next field of current; next field of current = new_element; }

//step 1 //step 1 //step 2 //step 3

Linked-List – Insertion Head

2

5

8

6

5

Curr New_Element

Head

2

5

∅

new_element = get a new element; data field of new_element = data;

New_Element

2

15

Step 1

Curr

Head

10

8

6

8

10

15

∅

Step 2 next field of New_Element = next field of current;

10

15

∅

6

Curr

Step 3 New Element

next field of current = new_element;

Linked-List – Warning: Fragile, Handle Links With Care • If one link is broken, you loose access to all subsequent elements. • What happens if you swap the following two lines in add: next field of new element = next field of current; next field of current = new_element;

//step 2 //step 3

next field of current = new_element; next field of new element = next field of current;

//step 2 //step 3

to

Head

2

5

8

10

15

∅

15

∅

7

Step 1

Curr

new_element = get a new element data field of new_element = data Head

2

5

New Element

8

10

7 Curr

Step 2 next field of current = new_element;

New Element

This part is no longer accessible

Step 3 next field of New_Element = next field of current; Head

2

5

8

7 Curr New Element

10

15

∅

Linked-List Delete an Element after current element void delete (handle current) { handle temp = next field of current; next field of current = next filed of next element of current // same as next field of temp discard temp }

Linked List - Deletion Head

5

6

handle temp = next field of current;

Head

5

9

Curr

6

next field of current = next filed of next element of current

15

∅

12

15

∅

temp

9

Curr

12

temp This element is no longer accessible

Garbage • When all access paths to a data object are destroyed but the data object continues to exist, the data object is said to be garbage. • Garbage is a less serious but still troublesome problem. A data object that has become garbage ties up storage that might otherwise be reallocated for another purpose. • A buildup of garbage can force the program to terminate prematurely because of lack of available free storage.

Head

5

6

9

Curr

12

temp This element is no longer accessible

15

∅

Garbage This part is no longer accessible

Head

2

5

8

7 Curr New Element

10

15

∅

Linked-lists Array Implementation • Handle is the index of the next element in the array struct node { element_type int };

data; // data next; // pointer to the next

Linked-lists Array Implementation class List { private: int head; int available; int size; node * NodeList; public: List (int s = 10); 10 ~List( ) { delete [ ] NodeList; } void printList(); int search (int data); bool add (int data); void remove (int data); }

// constructor - default size = // destructor

// add in ascending order // delete node from the list

Linked-lists – Array Implementation List::List(int s) { if (s <= 0) size = 10; else size = s; nodeList = new node [size]; for (int i = 0; i < size-1; i++) nodeList[i].next = i+1; nodeList [size-1].next = -1; available = 0; head = -1;

// create array // initialize // points to the next // last node – there is no next // -1 is used as φ

}

index 0 1 2 3 4 5 6 7 8 9 next 1 2 3 4 5 6 7 8 9 -1 available = 0 data - - - - - - - - - - head = -1

bool List::add (elem_type data) { int curr, prev, temp; if (available == -1) // check if space is available return false; else { temp = nodeList [available].next; // step 1 – initialize nodeList [available].data = data; prev = curr = head; // search – where to insert while (curr != -1 && nodeList [curr].data < data ) { prev = curr; curr = nodeList [curr].next; } nodeList [available].next = curr; // insert – step 2 if (curr == head) // insert – step 3: reset head head = available; else nodeList [prev].next = available; // insert – step 3 available = temp; // reset available return true; } }

Initial state (available = 0, head = -1) index 0 1 next 1 2 data - -

2 3 -

3 4 -

4 5 -

5 6 -

6 7 -

7 8 -

8 9 -

9 -1 -

7 8 -

8 9 -

9 -1 -

Add 5 (available = 1, head = 0) index 0 1 next -1 2 data 5 -

2 3 -

3 4 -

4 5 -

5 6 -

6 7 -

Add 7 (available = 2, head = 0) index 0 next 1 data 5

1 2 -1 3 7 -

3 4 -

4 5 -

5 6 -

6 7 -

7 8 -

8 9 -

9 -1 -

7 8 -

8 9 -

9 -1 -

Add 8 (available = 3, head = 0) index 0 next 1 data 5

1 2 7

2 3 -1 4 8 -

4 5 -

5 6 -

6 7 -

Add 6 (available = 4, head = 0) index 0 next 3 data 5

1 2 7

2 3 -1 1 8 6

4 5 -

5 6 -

6 7 -

7 8 -

8 9 -

9 -1 -

7 8 -

8 9 -

9 -1 -

Add 2 (available = 5, head = 4) index 0 next 3 data 5

1 2 7

2 3 -1 1 8 6

4 0 2

5 6 -

6 7 -

Add 7 (available = 1, head = 4) index 0 next 3 data 5

1 5 -

2 3 -1 2 8 6

4 0 2

5 6 -

6 7 -

7 8 -

8 9 -

9 -1 -

7 8 -

8 9 -

9 -1 -

Add 4 (available = 5, head = 4) index 0 next 3 data 5

1 0 4

2 3 -1 2 8 6

4 1 2

5 6 -

6 7 -

void List::remove (elem_type data) { int curr, prev; curr = prev = head; // search while (curr != -1 && l->nodeList [curr].data < data ) { prev = curr; curr = nodeList [curr].next; } if (curr != -1) { // if not end of list if (nodeList[curr].data == data) { // if found if (curr == head) { // if it is the first node head = nodeList[head].next; } else nodeList [prev].next = nodeList[curr].next; nodeList[curr].next = available; // add curr to available list avialable = curr; // reset available } } }

Delete 2 (available = 4, head = 1) index 0 next 3 data 5

1 0 4

2 3 -1 2 8 6

4 5 -

5 6 -

6 7 -

7 8 -

8 9 -

9 -1 -

8 9 -

9 -1 -

Delete 8 (available = 2, head = 1) index 0 next 3 data 5

1 0 4

2 4 -

3 4 -1 5 6 -

5 6 -

6 7 -

7 8 -

Linked List - Implementation using Dynamically Allocated Storage • Handle will be the pointer (memory address) of an element in the linked list. • Space may be acquired at run-time on request from free store using new. • At a point in time when a memory area pointed to by a pointer is no longer required, it can be returned back to free store using delete. • We should always return storage after we no longer need it. • Once an area is freed, it is improper and quite dangerous to use it.

Dangling References A dangling reference is an access path that continues to exist after the life time of the associated data object. ObjectTypeA *p, *q; p = new ObjectTypeA; q = p; delete q; q = NULL; What happens to p?

p q

p q

It’s a “dangling reference”!

φ

Garbage When all access paths to a data object are destroyed but the data object continues to exist, the data object is said to be garbage. ObjectTypeA *p, *q; p = new ObjectTypeA; q = new ObjectTypeA;

p q p

q = p; q What happens to the space that was pointed to by q? It’s “garbage”!

Dangling References and Garbage • Dangling references are particularly serious problem for storage management, as they might compromise the integrity of the entire run-time structure during program execution. • Garbage is a less serious but still troublesome problem. A data object that has become garbage ties up storage that might otherwise be reallocated for another purpose. • A buildup of garbage can force the program to terminate prematurely because of lack of available free storage.

Linked List - Implementation using Dynamically Allocated Storage struct Node { int Node };

data; *next;

Class LinkedList { private: Node * head; public: LinkedList() { head = NULL; } void add (int data); void remove (int data); void print (); ~LinkedList(); };

void LinkedList:: print() { Node *current = head; while (current != NULL) { cout << current->data; current = current->next; }

Head

2

curren t

5

8

10

15

∅

bool LinkedList::add(int data) { Node *temp = new Node; if (temp == NULL) return false; else { temp->data = data; Node *current, *previous; current = head; while (current != NULL && current->data < data;) { previous = current; current = current->next; } temp -> next = current; if (current == head) head = temp; else previous->next = temp; return true; } } Head

2

Previous

5

Current

8

10

temp 9

15

∅

void LinkedList::remove(int data) { Node *current, *previous; current = head; while (current != NULL && current->data < data) { previous = current; current = current->next } if (current != NULL && current->data == data) { if (current == head) head = head -> next; else previous->next = current->next; delete current; } }

Linked List Implementation of Stacks struct Node { int Node };

data; *previous;

Class Stack { private: Node * stk_ptr; public: Stack() { stk_ptr = NULL; } void push (int data); bool pop (int &data); bool isEmpty () { stk_ptr == NULL; } ~Stack(); };

Linked List Implementation of Stacks bool Stack::push (int data) { Node * temp = new Node; if (temp == NULL) return false; else { temp->data = data; temp->previous = stk_ptr; stk_ptr = temp; return true; } φ } Stk_ptr

temp

bool Stack::pop (int &data) { Node * temp = stk_ptr; if (!isEmpty()) { data = temp->data; stk_ptr = stk_ptr->previous; delete temp; return true; } else return false; }

φ

 Stk_ptr

temp

Linked List φ End of the linked list

• Can it be used to implement a queue? • How?

Start of the linked list

Linked List Implementation of Queues rear

front

φ End of the linked list

Start of the linked list

Assuming we maintain pointers to the first and the last node: Can we add before the first node in O(1)? Can we add after the last node in O(1)? Can we delete the last first node in O(1)? Can we delete the last last node in O(1)? Rear can be anywhere, but there is only one candidate for front!

The Destructor • The destructor is the counterpart of the constructor. • It is a member function that is called automatically when a class object goes out of scope. • Its purpose is to perform any cleanup work necessary before an object is destroyed. • Destructors are required for more complicated classes, where they're used to release dynamically allocated memory.

~LinkedList() { } struct Node { int data; Node *next; }; Class LinkedList {private: Node * head; public: … ~LinkedList(); }; LinkedList A; A.add(2); A.add(5); A.add(10); A.add(15); A.add(8);

 Head

2

5

8

A

• •

A goes out of scope. What Happens? When destructor is called, what is deleted?

•

What Happens to this memory area?

• •

It is garbage! Destructor must also delete this area.

10

15

∅

~LinkedList()

~LinkedList() { Node *temp1, *temp2; temp1 = head; while (temp1 != NULL) { temp2 = temp1->next; delete temp1; temp1 = temp2; } } 2 5 Head

      A

temp1

temp2

8

10

15

∅

A Function Returning An Object LinkedList emit() { LinkedList temp; temp.add(7); temp.add(20); temp.add(5); temp.add(8); // build the linked list return temp; } void usingEmit() { LinkedList myList = emit(); myList.add(2); }  

// what happens?

• This is illegal! Why? • Head of myList is a dangling reference!

• Just before leaving the function Head

2

5

8

10

15

∅

temp Head

“hidden temp”

• Just before resuming the calling function

  Head

temp Head

“hidden temp”

2

5

8

10

15

∅

Deep vs Shallow Copy • myList = yourList

Summary • • • •

Destructor Copy constructor Assignment operator overloading Check for out of memory condition

void LinkedList::add(int data) { Node *temp = new Node; temp->data = data; Node *current, *previous; current = head; while (current != NULL && current->data < data) { previous = current; current = current->next } temp -> next = current; if (current == head) head = temp; else previous->next = temp; }

void LinkedList::remove(int data) { Node *current, *previous; current = head; while (current != NULL && current->data < data) { previous = current; current = current->next; } if (current != NULL && current->data == data) { if (current == head) head = head -> next; else previous->next = current->next; delete current; } }

Eliminating Boundary Conditions – Dummy Head Node Class LinkedList { private: Node head; // instead of Node *head public: LinkedList() { head.next = NULL; } void add (int data); void remove (int data); void print (); ~LinkedList(); };

∅

Empty list

head 2

head

5

8

10

15

∅

void LinkedList:: print() { Node *current = head.next; while ( current != NULL) { cout << current->data; current = current->next; } }

void LinkedList::add(int data) { Node *temp = new Node; temp->data = data; Node *current, *previous; previous = &head; current = previous->next; while ( current != NULL && current->data < data) { previous = current; current = current->next } temp -> next = current; // if (current == head) head = temp; // take this out // else previous->next = temp; previous->next = temp; }

Linked-List Inserting a Node previous

current

2

5

8

10

15

head 1

temp->next = current; previous->next = temp;

temp

∅

void LinkedList::remove(int data) { Node *current, *previous; previous = &head; current = previous->next; while (current != NULL && current->data < data) { previous = current; current = current->next; } if (current != NULL && current->data == data) { // if (current == head) // head = head -> next; // else previous->next = current->next; delete current; } }

Linked-List Deleting a Node previous

current

 2

head

5

8

previous->next = current->next; delete current;

10

15

∅

Linked-List Deleting the Node pointed to by a pointer ‘p’, having no previous pointer p

2

5

8 10

head

p->data = p->next->data; t = p->next; p->next = p->next->next; delete t;

t

 10

15

∅

Boundary Conditions • •

Can we delete the first node? Can we delete the last node?

Linked-List Deleting the Node pointed to by a pointer ‘p’, having no previous pointer

Dummy Tail Node Class LinkedList { private: Node head; Node *tail; public: LinkedList() { tail = new Node; head.next = tail; } … };

tail head

Empty list

tail head 2

5

8

10

15

Why do we have tail as pointer to a node whereas head is a node?

Linked-List Deleting the Node pointed to by a pointer ‘p’, having no previous pointer if (p->next == tail) { // deleting the last node delete tail; tail = p; } else { // otherwise p->data = p->next->data; t = p->next; p->next = p->next->next; delete t; }

p

head 2

5

8

10

15

tail



Linked-List Deleting the Node pointed to by a pointer ‘p’, having no previous pointer p->data = p->next->data; t = p->next; p->next = t->next; delete t;

5 7

12

Boundary Conditions • •

Where is the starting point? What happens when we delete the node pointed to by the head?

Circular Linked-List

9

10 8 3

10

p

t

Can be with or without the dummy head node

Circular Linked List Class CircularList { private: Node head; // instead of Node *head public: CircularList() { head.next = &head; } void add (int data); void remove (int data); void print (); ~CircularList(); };

head

void CircularList::add(int data) { Node *temp = new Node; temp->data = data; Node *current, *previous; previous = &head; current = previous->next; while ( current != &head && current->data < data ) { current = current->next ; previous = current; } temp -> next = current; previous->next = temp; }

2

head

5

8

10

15

Advantages • Every node is accessible from any node. • That is, from a given node, all nodes can be reached by simply following the links. • Example: Round Robin Queue for resource sharing such as process scheduling

Doubly Linked-List • Some times it is important to be able to go back and forth from a given point in the list. • We can achieve it with the help of doubly linked lists.

struct DoubleListNode { int data; DoubleListNode *next; DoubleListNode *previous; };

In a doubly linked list, at any node pointed to by “p” we have the following:

p == p->next->previous p == p->previous->next

Doubly Linked-List Class DoublyLinkedList { private: DoubleListNode head; public: DoublyLinkedList() { head.next = head.previous = &head; } void add (int data); void remove (int data); void print (); ~DoublyLinkedList(); };

Doubly Linked-List

2

5

7

10

15

Doubly Linked-List Inserting a Node

2

5

current

7

10

15

p->previous = current;

6

p->next = current->next; current->next->previous = p;

p

current->next = p;

Order is very important!

Doubly Linked-List Inserting a Node Undesirable links

2

5

current

7

6

p

10

15

p->previous = current; p->next = current->next; current->next = p; current->next->previous = p;

Doubly Linked-List Deleting a Node

2

5

 7

10

current current->previous->next = current->next; current->next ->previous = current->previous; delete current;

15