Lec 04
Lec 04
Lec 04
04
Data Structures
C++ Code for Linked List
// position current before the first
// list element
void start() {
lastCurrentNode = headNode;
currentNode = headNode;
};
C++ Code for Linked List
void remove() {
if( currentNode != NULL &&
currentNode != headNode) {
lastCurrentNode->setNext(currentNode->getNext());
delete currentNode;
currentNode = lastCurrentNode->getNext();
size--;
}
};
currentNode
headNode
2 6 8 7 1 size=5
lastcurrentNode
C++ Code for Linked List
void remove() {
if( currentNode != NULL &&
currentNode != headNode) {
1 lastCurrentNode->setNext(currentNode->getNext());
delete currentNode;
currentNode = lastCurrentNode->getNext();
size--;
}
};
currentNode
headNode
1
2 6 8 7 1 size=5
lastcurrentNode
C++ Code for Linked List
void remove() {
if( currentNode != NULL &&
currentNode != headNode) {
1 lastCurrentNode->setNext(currentNode->getNext());
2 delete currentNode;
currentNode = lastCurrentNode->getNext();
size--;
}
};
currentNode
headNode
1
2 8 7 1 size=5
2
lastcurrentNode
C++ Code for Linked List
void remove() {
if( currentNode != NULL &&
currentNode != headNode) {
1 lastCurrentNode->setNext(currentNode->getNext());
2 delete currentNode;
3 currentNode = lastCurrentNode->getNext();
4 size--;
}
3
};
currentNode
headNode
1 4
2 8 7 1 size=4
2
lastcurrentNode
C++ Code for Linked List
int length()
{
return size;
};
private:
int size;
Node *headNode;
Node *currentNode, *lastCurrentNode;
Example of List Usage
#include <iostream>
#include <stdlib.h>
#include "List.cpp"
head 2 6 8 7 1 size=5
current
Doubly-linked List
1. newNode->setNext( current->getNext() );
current
head 2 6 8 7 1 size=5
newNode 9 1
Doubly-linked List
1. newNode->setNext( current->getNext() );
2. newNode->setprev( current );
current
head 2 6 8 7 1 size=5
newNode 9 1
Doubly-linked List
1. newNode->setNext( current->getNext() );
2. newNode->setprev( current );
3. (current->getNext())->setPrev(newNode);
current
head 2 6 8 7 1 size=5
2 3
newNode 9 1
Doubly-linked List
1. newNode->setNext( current->getNext() );
2. newNode->setprev( current );
3. (current->getNext())->setPrev(newNode);
4. current->setNext( newNode );
current
head 2 6 8 7 1 size=5
2 4 3
newNode 9 1
Doubly-linked List
1. newNode->setNext( current->getNext() );
2. newNode->setprev( current );
3. (current->getNext())->setPrev(newNode);
4. current->setNext( newNode );
5. current = newNode;
6. size++;
head 2 6 8 7 1 size=6
2 4 3
newNode 9 1
current
Circularly-linked lists
The next field in the last node in a singly-linked
list is set to NULL.
Moving along a singly-linked list has to be done
in a watchful manner.
Doubly-linked lists have two NULL pointers:
prev in the first node and next in the last node.
A way around this potential hazard is to link the
last node with the first node in the list to create
a circularly-linked list.
Circularly-linked lists
The next field in the last node in a singly-linked
list is set to NULL.
Moving along a singly-linked list has to be done
in a watchful manner.
Doubly-linked lists have two NULL pointers:
prev in the first node and next in the last node.
A way around this potential hazard is to link the
last node with the first node in the list to create
a circularly-linked list.
Circularly-linked lists
The next field in the last node in a singly-linked
list is set to NULL.
Moving along a singly-linked list has to be done
in a watchful manner.
Doubly-linked lists have two NULL pointers:
prev in the first node and next in the last node.
A way around this potential hazard is to link the
last node with the first node in the list to create
a circularly-linked list.
Circularly-linked lists
The next field in the last node in a singly-linked
list is set to NULL.
Moving along a singly-linked list has to be done
in a watchful manner.
Doubly-linked lists have two NULL pointers:
prev in the first node and next in the last node.
A way around this potential hazard is to link the
last node with the first node in the list to create
a circularly-linked list.
Cicularly Linked List
Two views of a circularly linked list:
current
head 2 6 8 7 1 size=5
current
6
8
size=5
head 2
1
Josephus Problem
A case where circularly linked list comes in
handy is the solution of the Josephus Problem.
Josephus Problem
A case where circularly linked list comes in
handy is the solution of the Josephus Problem.
Consider there are 10 persons. They would like
to choose a leader.
Josephus Problem
A case where circularly linked list comes in
handy is the solution of the Josephus Problem.
Consider there are 10 persons. They would like
to choose a leader.
The way they decide is that all 10 sit in a circle.
Josephus Problem
A case where circularly linked list comes in
handy is the solution of the Josephus Problem.
Consider there are 10 persons. They would like
to choose a leader.
The way they decide is that all 10 sit in a circle.
They start a count with person 1 and go in
clockwise direction and skip 3. Person 4
reached is eliminated.
Josephus Problem
A case where circularly linked list comes in
handy is the solution of the Josephus Problem.
Consider there are 10 persons. They would like
to choose a leader.
The way they decide is that all 10 sit in a circle.
They start a count with person 1 and go in
clockwise direction and skip 3. Person 4
reached is eliminated.
The count starts with the fifth and the next
person to go is the fourth in count.
Josephus Problem
A case where circularly linked list comes in
handy is the solution of the Josephus Problem.
Consider there are 10 persons. They would like
to choose a leader.
The way they decide is that all 10 sit in a circle.
They start a count with person 1 and go in
clockwise direction and skip 3. Person 4
reached is eliminated.
The count starts with the fifth and the next
person to go is the fourth in count.
Eventually, a single person remains.
Josephus Problem
A case where circularly linked list comes in
handy is the solution of the Josephus Problem.
Consider there are 10 persons. They would like
to choose a leader.
The way they decide is that all 10 sit in a circle.
They start a count with person 1 and go in
clockwise direction and skip 3. Person 4
reached is eliminated.
The count starts with the fifth and the next
person to go is the fourth in count.
Eventually, a single person remains.
Josephus Problem
N=10, M=3
4
3 5
2 6
1
7
10
8
9
Josephus Problem
N=10, M=3
eliminated
4
3 5
2 6
1
7
10
8
9
Josephus Problem
N=10, M=3
eliminated
4
3 5
8
2 6
1
7
10
9
Josephus Problem
N=10, M=3
eliminated
4
3 5
8
6
2
1
7
10
9
Josephus Problem
N=10, M=3
eliminated
4
3 5
8
6
2
1 7
10
9
Josephus Problem
N=10, M=3
eliminated
4
5
8
6
2
1 7
3
10
9
Josephus Problem
N=10, M=3
eliminated
4
5
8
6
2
1 7
10
9
Josephus Problem
N=10, M=3
eliminated
4
5
8
6
2
1 7
10
9
Josephus Problem
N=10, M=3
eliminated
4
5
8
6
2
10
1
Josephus Problem
N=10, M=3
eliminated
4
5
8
10
6
Josephus Problem
#include "CList.cpp"
void main(int argc, char *argv[])
{
CList list;
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i);
list.start();
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl;
}
Josephus Problem
#include "CList.cpp"
void main(int argc, char *argv[])
{
CList list;
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i);
list.start();
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl;
}
Josephus Problem
#include "CList.cpp"
void main(int argc, char *argv[])
{
CList list;
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i);
list.start();
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl;
}
Josephus Problem
#include "CList.cpp"
void main(int argc, char *argv[])
{
CList list;
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i);
list.start();
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl;
}
Josephus Problem
#include "CList.cpp"
void main(int argc, char *argv[])
{
CList list;
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i);
list.start();
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl;
}
Josephus Problem
#include "CList.cpp"
void main(int argc, char *argv[])
{
CList list;
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i);
list.start();
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl;
}
Josephus Problem
#include "CList.cpp"
void main(int argc, char *argv[])
{
CList list;
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i);
list.start();
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl;
}
Josephus Problem
#include "CList.cpp"
void main(int argc, char *argv[])
{
CList list;
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i);
list.start();
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl;
}
Josephus Problem
#include "CList.cpp"
void main(int argc, char *argv[])
{
CList list;
int i, N=10, M=3;
for(i=1; i <= N; i++ ) list.add(i);
list.start();
while( list.length() > 1 ) {
for(i=1; i <= M; i++ ) list.next();
cout << "remove: " << list.get() << endl;
list.remove();
}
cout << "leader is: " << list.get() << endl;
}