Answers/Solutions to Exercises in Chapter 9, Exercise 8

E8: Using two arrays of size N, implement a serialized version of a doubly linked list of integers in the range 0..N-1.

S8:  A sample program is below:

#define null -1

int N=10;
int* next;
int* prev;
int start;

void create()
{
	int i;

	next=(int*)malloc(sizeof(int)*N);
	for(i=0; i<N; next[i++]=null);
	prev=(int*)malloc(sizeof(int)*N);
	for(i=0; i<N; prev[i++]=null);
	start=null;
}


void insert(int a) // at the end
{
	if (start==null) {
		start=a;
		return;
	}
	for(int i=start; next[i]!=null; i=next[i]);
	next[i]=a;
	next[a]=null;
	prev[a]=i;
}

void remove(int a) // remove element a
{
	int i1, i;

	if (a==start) {
		start=next[a];
		prev[next[a]]=null;
		next[a]=null;
		return;
	}
	for(i1=start,i=next[start]; i!=null; i1=i,i=next[i]) {
		if (a==i) {
			next[i1]=next[a];
			if (next[a]!=null) prev[next[a]]=i1;
			prev[i]=null;
			next[i]=null;
			return;
		}
	}
}
			

void show()
{
	int i;
	if (start==null) 
		printf("<empty>\n");
	for(i=start; i!=null; i=next[i])
		printf("%d ",i);
	putchar('\n');
}




int main()
{
	create();
	show();
	insert(3);
	insert(7);
	insert(1);
	show();

	remove(3);
	show();
	remove(7);
	show();
	remove(1);
	show();
	return 0;
}

The output of the sample program:

<empty>

3 7 1
7 1
1
<empty>

Back to Answers/Solutions Index                          Back to Answers/Solutions for Chapter 9 Index