Data Structure

Lebanese University – Faculty of Engineering III

Linked Lists
Dr. Ali El Masri

1
Part A

2
Array Definition
• An array is a sequenced collection of variables all of the same type

• Each variable, or cell, in an array has an index, which uniquely refers to the value stored in that cell

• The cells of an array, A, are numbered 0, 1, 2, and so on

• Each value stored in an array is often called an element of that array

• Since the length of an array determines the maximum number of things that can be stored in the array, we will sometimes
refer to the length of an array as its capacity

3
An array can store primitive elements, such as characters

An array can also store pointers to objects

4
First way: Declaration and Initialization
The first way to create an array is to use an assignment to a literal form when initially declaring the array, using a syntax as:

elementType arrayName[] = {initialValue0, initialValue1, …, initialValueN-1};

The elementType can be any C++ base type or class name, and arrayName can be any valid C++ identifier

The initial values must be of the same type as the array.

Second way: Declaration without Initialization

elementType arrayName[arraySize];

In both ways, array size is specified at the moment of array declaration and cannot be changed during the program run time

5
• Data collection

• Pre-determined fixed size

• Must be specified at the moment of array declaration

• No space overhead
• Size = length * sizeof(element)

• Elements of the array are stored in contiguous memory locations

• Easy access to any element in constant time O(1)

• It takes the same time to access a[1] or a[10]
• The address of a[x] can be determined arithmetically by adding an offset to the machine address of the head
of the array
++ Fast element access
-- Impossible to resize
• However,
• Many applications require resizing!
• Required size not always immediately available 6
Part B

7
• A linked list is a fundamentally different way of storing collections

• A linked list is a series of connected nodes, where each node is a data structure

• Each node contains:

• One or more members that represent data
• A pointer (link) to the next node in the list

Node

Linked List

• Elements are NOT stored in contiguous memory locations

8
• Data collection

• No fixed size
• can easily grow or shrink in size during the program run time

• Space overhead
• Each element must store an additional pointer
• Size = length * sizeof(element) + length * sizeof(pointer)

• Elements of the list are NOT stored in contiguous memory locations

• No Easy access to the i-th element of the list

• Need to traverse the list starting from the head of the list and passing by all previous nodes

-- No fast element access

++ Possibility of resizing
9
Part C

10
To implement a linked list, we need two C++ classes:

• One class to implement the node

• One class to implement the list

Object of the
Linked List class

An example of a linked list Object of

having a single pointer pointing the Node
the first node of the list class

11
This is another way to implement a linked list

Object of the
Linked List class

An example of a linked list having: Object of

• One pointer pointing to the first node of the list the Node
• One pointer pointing to the last node of the list class

12
One more way to implement a linked list

Object of
Object of the the Node
We are going to Linked List class class
implement this
example

An example of a linked list having:

• One pointer pointing to the first node of the list
• One pointer pointing to the last node of the list
• One variable saving the size of the list
13
Linked List Node

Since each node has a single

pointer, this kind of lists is
called Singly Linked List

14
 Data: Any type of data (C++ or user-
defined) can be used. For simplicity,
SLLNode.h we consider the int type.

class SLLNode {
private: Pointer to next node
int data;
SLLNode* next;
public:
SLLNode(int dataValue, SLLNode* nextNode);

friend class SinglyLinkedList; Constructor

};

SLLNode.cpp
To let the SinglyLinkedList #include "SLLNode.h"
class access private
variables of the SLLNode
class SLLNode::SLLNode(int dataValue, SLLNode* nextNode) {
data = dataValue;
next = nextNode;
}
Implementation of
the constructor 15
 SinglyLinkedList.h
class SinglyLinkedList { Pointer to first node in the list
private:
SLLNode* head; Pointer to last node in the list
SLLNode* tail; Number of nodes in the list
int size;
public:
SinglyLinkedList();
Add a node at the Constructor
beginning of the list ~SinglyLinkedList();
void addToHead(int data); Destructor
Add a node at the end void addToTail(int data);
of the list void addAtIndex(int index, int data);
int removeFromHead();
Add a node at a given
place in the list int removeFromTail(); Remove a node from the
int removeFromIndex(int index); beginning of the list
bool isEmpty();
Check if the list is Remove a node from the
empty bool isInList(int data); end of the list
void print();
int getSize(); Remove a node from a
Print the content of given place in the list
};
the list

Get the size of the list Check if a node is in the list

16
SinglyLinkedList::SinglyLinkedList() {

head = NULL;
tail = NULL;
Constructor: Linked-List initialization
size = 0;

17
 List before adding the new node

Steps: Implementation:
Allocate new node

SLLNode* newNode = new SLLNode(data, NULL);

Insert new element

Have next of new node pointing to newNode->next = head;

old head

Update head to point to new node head = newNode;

head = new SLLNode(data, head);

18
void SinglyLinkedList::addToHead(int data) { Special case: Empty list

if (size == 0)
head = tail = new SLLNode(data, NULL);

else
head = new SLLNode(data, head);

size++;
}

Increment the list size

19
 List before adding the new node

Steps: Implementation:
Allocate a new node

Insert new data

SLLNode* newNode = new SLLNode(data, NULL);

Have next of new node pointing to NULL

Have next of old tail pointing to new node tail->next = newNode;

Update tail to point to new node tail = newNode;

20
 void SinglyLinkedList::addToTail(int data) {

SLLNode* newNode = new SLLNode(data, NULL);

if (size == 0) { Allocate a new node

Insert new data
Special case: Empty list head = tail = newNode; Have next of new node pointing to NULL

} else {
Have next of old tail pointing to new node
tail->next = newNode;
tail = newNode;

}
Update tail to point to new node
size++;

}
Increment the list size
21
List before removing the new node

Steps: Implementation:

Update head to point to its next SLLNode* oldHead = head;

(2nd node in the list) head = head->next;

Delete the old head delete oldHead;

22
 int SinglyLinkedList::removeFromHead() {

Special case: Empty list if (size == 0)

return -1;

Save data of old head int data = head->data;

Special case: List consisting of a single node
if (size == 1) {
delete head;
head = tail = NULL;
}
Create a pointer to old head else { Update head to point to its next (2nd
SLLNode* oldHead = head; node in the list)
head = head->next;
delete oldHead;
Returns the data } Delete old head
of the old head
size--;
return data;
}
Decrement the list size
23
 Steps: Implementation:
Create a temporary pointer SLLNode* tmp = head;
pointing to the head

while (tmp->next != tail) {

Traverse the list and stop at tmp = tmp->next;
the predecessor of the tail }

Delete old tail delete tail;

Have tail point to the temporary node

tail = tmp;

Update tail to point to NULL tail->next = NULL;

24
 int SinglyLinkedList::removeFromTail() {
if (size == 0)
Special case: Empty list return -1; Save data of old tail

int data = tail->data;

if (size == 1) { Special case: List consisting of a single node

delete tail;
head = tail = NULL;
}
else {
Create a temporary Traverse the list and stop at
SLLNode* tmp = head;
pointer pointing to head the predecessor of the tail
while (tmp->next != tail) {
tmp = tmp->next;
}
Have tail point to the temporary node
Delete old tail delete tail;
tail = tmp;
tail->next = NULL; Update next of tail to point to NULL
}
Decrement the list size
size--;
Return data of old tail
return data;
} 25
Removing at the tail of a singly linked list is not efficient!

There is no constant-time way to update the tail to point to the previous node

We have to traverse the whole list in order to have a pointer to the predecessor of the tail

26
 Steps: Allocate a new node Implementation:
SLLNode* newNode = new SLLNode(data, NULL);
Insert new data

Create a temporary pointer pointing to SLLNode* tmp = head;

the head

int i = 0;
while (i < index - 1) {
Traverse the list and stop at (index – 1) tmp = tmp->next;
i++;
}

Update the next of new node

to point to the next of the node newNode->next = tmp->next;
at (index – 1)

Update next of node at (index – 1)

tmp->next = newNode;
to point to the new node
27
void SinglyLinkedList::addAtIndex(int index, int data) {

SLLNode* newNode = new SLLNode(data, NULL); Allocate a new node

Insert new data
if (index == 0) { Special case: Insert Create a temporary pointer
addToHead(data); at the beginning pointing to the head
return; int i = 0;
}
SLLNode* tmp = head;
if (index >= size) { while (i < index - 1) {
Traverse the list and
addToTail(data); tmp = tmp->next;
stop at (index – 1)
return; i++;
} }

Update the next of new node to newNode->next = tmp->next;

Special case: Insert point to the next of the node at
at the end (index – 1) tmp->next = newNode;

size++; Increment the list size

Update next of node at (index – 1)
}
to point to the new node 28
 Steps: Implementation:

Create two temporary nodes starting at SLLNode* tmp = head;

head SLLNode* pred = NULL;

• Traverse the list and stop at

the given index while (i < index) {
pred = tmp;
• One node points the node at (index) and
tmp = tmp->next;
the other node points at (index – 1) i++;
}
Have next of node at (index – 1) point
pred->next = tmp->next;
to node at (index + 1)

Delete node at index delete tmp;

29
int SinglyLinkedList::removeFromIndex(int index) {

if (size == 0 || index >= size) Create two temporary

Special case: Out
return -1; nodes starting at the head
of bound index
if (index == 0) {
int data = removeFromHead(); int i = 0;
return data;
} Special case: Insert SLLNode* tmp = head;
at the beginning SLLNode* pred = NULL;
if (index == size - 1) {
int data = removeFromTail(); while (i < index) {
return data; pred = tmp;
} tmp = tmp->next;
Traverse the list and
i++;
stop at the given index }
Special case: Insert
at the end One node points the node at index pred->next = tmp->next;
and the other node points at index – 1
int data = tmp->data;
delete tmp;
Have node at (index – 1) point Delete old node and
to the node at (index + 1) size--; return its data
return data; 30
Decrement the list size }
 bool SinglyLinkedList::isInList(int data) {

if (size == 0)
Special case: Empty list cout << "Empty list" << endl;

SLLNode* tmp = head; Create a temporary

pointer pointing to head
Traverse the whole list while (tmp != NULL) {
if (tmp->data == data)
return true; If data found, return true
tmp = tmp->next;
}

return false; If data not found, return false

}

31
void SinglyLinkedList::print() {
if (size == 0)
cout << "Empty list" << endl;
else {
cout << "List: ";
SLLNode* tmp = head; int SinglyLinkedList::getSize() {
while (tmp != NULL) { return size;
cout << tmp->data << " --> "; }
tmp = tmp->next;
}
cout << " NULL " << endl;
}
} bool SinglyLinkedList::isEmpty() {
return size == 0;
}
SinglyLinkedList::~SinglyLinkedList() {
while (size != 0)
removeFromHead();
}

32
int SinglyLinkedList::getHead() {
if (size == 0)
return -1;
return head->data;
}

int SinglyLinkedList::getTail() {
if (size == 0)
return -1;
return tail->data;
}

33
 Method Running time
addToHead(int data) O(1)
addToTail(int data) O(1)
addAtIndex(int index, int data) O(n)
removeFromHead() O(1)
removeFromTail() O(n)
removeFromIndex(int index) O(n)

34
Part D

35
• A doubly linked list can be traversed forward and backward

• Each node contains:

• One or more members that represent data
• A pointer (link) to the next node in the list
• A pointer (link) to the previous node in the list

36
 Data: Any type of data (C++ or user-
defined) can be used. For simplicity,
DLLNode.h we consider the int type.

class DLLNode {
private: Pointer to next node
int data;
DLLNode* next;
DLLNode* prev; Pointer to previous node
public:
DLLNode(int dataValue, DLLNode* nextNode, DLLNode* prevNode); Constructor
To let the DoublyLinkedList
friend class DoublyLinkedList; class access private variables
}; of the DLLNode class

DLLNode.cpp
#include "DLLNode.h"
DLLNode::DLLNode(int dataValue, DLLNode* nextNode, DLLNode* prevNode) {
data = dataValue;
next = nextNode;
Implementation of
prev = prevNode; the constructor
}
37
 DoublyLinkedList.h
class DoublyLinkedList { Pointer to first node in the list
private:
DLLNode* head; Pointer to last node in the list
DLLNode* tail; Number of nodes in the list
int size;
public:
DoublyLinkedList();
Add a node at the Constructor
beginning of the list ~DoublyLinkedList();
void addToHead(int data); Destructor
Add a node at the end void addToTail(int data);
of the list void addAtIndex(int index, int data);
int removeFromHead();
Add a node at a given
place in the list int removeFromTail(); Remove a node from the
int removeFromIndex(int index); beginning of the list
bool isEmpty();
Check if the list is Remove a node from the
empty bool isInList(int data); end of the list
void print();
int getSize(); Remove a node from a
Print the content of given place in the list
};
the list

Get the size of the list Check if a node is in the list 38

 List before inserting the new node

Allocate new node

Insert new data

Have next of the new node

tail = new DLLNode(data, NULL, tail);
point to NULL

Have previous of new

node point to old tail

Have tail point to new

node

Have next of old tail point

tail->prev->next = tail;
to new tail 39
 void DoublyLinkedList::addToTail(int data) {

if (size == 0)
Special case:
Empty list head = tail = new DLLNode(data, NULL, NULL);

else {

tail = new DLLNode(data, NULL, tail);

Regular case:
Discussed in the tail->prev->next = tail;
previous slide
}

size++;
} Increment list size

40
List before removing the new node

Steps: Implementation:

Have tail point to the previous of the

tail = tail->prev;
old tail

Delete old tail delete tail->next;

Have next of tail point to NULL tail->next = NULL;

41
 int DoublyLinkedList::removeFromTail() {
Special case: Empty list
if (size == 0)
return -1;
Save data of old tail Unlike Singly Linked List:
int data = tail->data;
Special case: List consisting • Removing at the tail of a doubly linked
of a single node if (size == 1) { list is efficient!

Delete old tail delete head; • It can be performed in constant time

head = tail = NULL;
Have head and tail point to • We do NOT have to traverse the whole
NULL } else { list in order to have a pointer to the
predecessor of the tail
Regular case: Discussed in tail = tail->prev;
the previous slide delete tail->next; Running time of removeFromHead() is O(1)
tail->next = NULL; It is O(n) in case of Singly Linked List

}
Decrement the list size size--;
return data; Return data of old tail
42
}
Part E

43
A linked list in which the last node points to the first node

In a circular linked list with more than one node, it is convenient to make the pointer first point to the last node of the list

Then by using first you can access both the first and the last node of the list

For example, first points to the last node and first->next points to the first node

We can traverse the whole list by starting from any node (we just need to stop when the first visited node is visited again)

44
Part F

45
Exercise 1: Write a method (to be added to the SinglyLinkedList class) that takes as parameter an integer (int index).
The method should return the sum of all nodes after the specified index. You can use any of the methods of the
class SinglyLinkedList:

int SinglyLinkedList::SumAfterIndex(int index) {

// missing codes

Exercise 2: Write a method (to be added to the SinglyLinkedList class) that takes as parameters two linked lists and
appends the second list at the end of the first one. You can use any of the methods of the class SinglyLinkedList:

void SinglyLinkedList::append(SinglyLinkedList* sll1, SinglyLinkedList* sll2) {

// missing codes

46
Exercise 3: Implement the method “void addAtIndex(int index, int data){}” for the DoublyLinkedList class. Assume
that the method “void addAtHead(int data){}” and the method “void addAtTail(int data){}” are already implemented.
void DoublyLinkedList::addAtIndex(int index, int data) {

// missing codes

Exercise 4: Implement the method “int removeFromIndex(int data){}” for the DoublyLinkedList class. Assume that
the method “int removeFromHead(){}” and the method “int removeFromTail(){}” are already implemented.

int DoublyLinkedList::removeFromIndex(int index) {

// missing codes

47
Part G

48
• Data Structures and Algorithms in C++, 4th Edition, Adam Drozdek

• Data Structures & Algorithm Analysis in C++, 4th Edition, by M.A. Weiss

• Data Structures and Algorithms in C++, 2nd Edition, by M.T. Goodrich, R. Tamassia, and D.M. Mount

• Data Structures and Algorithms in Java, 6th Edition, by M.T. Goodrich and R. Tamassia

• Data Structures and Program Design in C++, 1st Edition, by R.L. Kruse and A.J. Ryba

49