The Josephus Problem

• N people, numbered from 1 to N, form a circle. Counting starts at person 1 and - proceeding around the circle - every Kth person has to leave, until only one is left.
• Given N and K, who will be the last?

First attempt

for (i=1 to N) circle[i] = true;
position = 0;
for i=1 to N-1 {
  // move forward K steps
  for j=1 to K {
    position = (position mod N)+1;
    while (circle[position]==false) {
      position = (position mod N)+1;
    }
  }
  // delete from circle
  circle[position] = false;
}
for i=1 to N {
  if (circle[i]==true) print(i);
}

• Very inefficient solution
• Skipping over empty positions wastes time.

Linked Lists

• Like an array, a list also is a container datatype.
• List elements consist of a value and a pointer to the next list element.
• The list itself is represented by a pointer to the first list element.

Elementary Operations

• Defining the shape of a list element.

  class ListElement {
    int value;
    ListElement* next;
  }
  

• Creating a new (empty) list element.

  ListElement* p = new ListElement;
  

• Setting the value and/or pointer of an element.

  p->value = 42;
  p->next = NULL;
  

• Destroying a list element.

  delete p;

Standard Operations

• Inserting an element into a list.
• Removing an element from a list.

Implementing a stack with a linked list

ListElement* top_of_stack = NULL;

void push (int x) {
  ListElement* p = new ListElement;
  p->value = x;
  p->next = top_of_stack;
  top_of_stack = p;
}
        
int pop() {
  ListElement* p = top_of_stack;
  int x = p->value;
  top_of_stack = top_of_stack->next;
  delete p;
  return x;
}

Implementing a queue with a linked list

ListElement* head = NULL;
ListElement* tail = NULL;

void enqueue (int x) {
  ListElement* p = new ListElement;
  p->value = x;
  p->next = NULL;
  if (head==NULL)
    head = p;
  else
    tail->next = p;
  tail = p;
}

int dequeue (int x) {
  ListElement* p = head;
  int x = p->value;
  head = head->next;
  if (head==NULL) tail = NULL;
  delete p;
  return x;
}

Solving the Josephus Problem with a linked list

for (i=1 to N) enqueue(i); 
tail->next = head;
position = tail;
while (position->next != position) {
  for (i=1 to K-1) position = position->next;
  position->next = position->next->next;
}
print(position->value);

Double Linked Lists

class ListElement {
  int value;
  ListElement* next;
  ListElement* prev;
}

• A second pointer that points to the previous element makes it possible to go forward and backward in the list.

Binary Trees

class TreeElement {
  int value;
  TreeElement* parent;
  TreeElement* left;
  TreeElement* right;
}

Implementing a stack with an array

int stack[MAX_STACK_SIZE];
int top_of_stack = 0;

void push (int x) {
  stack[top_of_stack] = x;
  top_of_stack++;
}  

int pop () {
  top_of_stack--;
  return stack[top_of_stack];
}

Implementing a queue with an array

int queue[MAX_QUEUE_SIZE];
int head = 0;
int tail = 0;

void enqueue (int x) {
  queue[tail] = x;
  tail = (tail+1)%MAX_QUEUE_SIZE;
}

void dequeue () {
  int x = queue[head];
  head = (head+1)%MAX_QUEUE_SIZE;
  return x;
}

Abstract and Concrete Datatypes

• Arrays, lists and trees are concrete datatypes. They are basic data structures typically provided by the computer language.
• Stacks, queues and heaps are abstract datatypes. They are just ideas, i.e. "black boxes" with a defined behavior. To implement them, you have to choose a suitable concrete datatype.
• In particular, stacks and queues can be implemented by arrays or linked lists.
• A heap can be implemented by an array or a binary tree.

Last modified 2001-02-04