1. linked_lists.txt
2. liste.c
3. liste1.c
4. liste_NULL.c
5. stack.c
6. stack_t.c
7. stack_t.cpp
8. stack_t1.cpp

linked Lists
consists of nodes with link to next node
dummy nodes head and tail to make operations easy

Advantage over arrays:
Linked Lists can grow and shrink during their lifetime (size need not to be
known at the start)
flexibillity to rearrange efficiently (quick access to any arbitrary element)


common operations on lists:
init
insert 
delete

kinds of list/common operations: 

stacks (push, pop, top) 

queues (append at the end, get first element)


problems:
access to an arbitary node
-> insert causes walk through the entire list 
-> insert_after function with node pointer as parameter
-> double linked list (node* pre) makes access to preciding element of a node easy

parametrized lists (flexible type of elements to store - int values, arrays, structs, lists)
-> typedef declaration, problems with the initialization of elements in insert and append, how to do?
-> class list wich uses object node, node can have multiple constructor functions to initialize values
of different types

initialization of more then one list (liste1.c)
-> l1 and l1 will be mixed because the same memory area is used
-> solution is encapsulation in objects
 

#include <stdio.h>
#include <stdlib.h>

struct node {
	int value;
	struct node *next;
	};

struct node *head;
struct node *tail;

init(void) {
	head=(struct node *) malloc(sizeof *head);
	tail=(struct node *) malloc(sizeof *head);
	head->next = tail; tail->next = tail;
}

struct node *append(int v) {
	struct node *ptr;
	struct node *t;
	ptr=head;
	while (ptr->next != tail) ptr = ptr->next;
	t=(struct node *) malloc(sizeof *t);
	t->value=v;
	t->next = tail;
	ptr->next = t;
	return ptr;
}

struct node *insert(int v, struct node *ptr) {
	struct node *t;
	t=(struct node *) malloc(sizeof *t);
	t->value=v;
	t->next = tail;
	ptr->next = t;
	return ptr;
	}	
	
void delete(struct node *ptr) {
	struct node *t;
	t = ptr->next;
	ptr->next = ptr->next->next;
	free(t);
	}
	


int main () {
struct node *ptr;

init();

ptr=append(10);
ptr=append(20);
ptr=append(30);
ptr=append(40);
ptr=append(50);

ptr=insert(60, ptr);
delete(ptr);

ptr=head->next;
while (ptr != tail) {
	printf("%d\n",ptr->value);
	ptr = ptr->next;
	}
}	 

#include <stdio.h>
#include <stdlib.h>

struct node {
	int value;
	struct node *next;
	};

struct node *head;
struct node *tail;

struct node *init(void) {
	head=(struct node *) malloc(sizeof *head);
	tail=(struct node *) malloc(sizeof *head);
	head->next = tail; tail->next = tail;
	return head;
}

struct node *append(int v) {
	struct node *ptr;
	struct node *t;
	ptr=head;
	while (ptr->next != tail) ptr = ptr->next;
	t=(struct node *) malloc(sizeof *t);
	t->value=v;
	t->next = tail;
	ptr->next = t;
	return ptr;
}

struct node *insert(int v, struct node *ptr) {
	struct node *t;
	t=(struct node *) malloc(sizeof *t);
	t->value=v;
	t->next = tail;
	ptr->next = t;
	return ptr;
	}	
	
void delete(struct node *ptr) {
	struct node *t;
	t = ptr->next;
	ptr->next = ptr->next->next;
	free(t);
	}
	


int main () {
struct node *l1, *l2;
l1=init();
l2=init();

l1=append(1);
l1=append(2);
l1=append(3);
l1=append(4);
l1=append(5);

l1=insert(6, l1);
delete(l1);

l2=append(10);
l2=append(20);
l2=append(30);
l2=append(40);
l2=append(50);

l2=insert(60, l2);
delete(l2);

l1=head->next;
while (l1 != tail) {
	printf("%d\n",l1->value);
	l1 = l1->next;
	}






}	 

#include <stdio.h>
#include <stdlib.h>

struct list {
	int value;
	struct list *next;
	};

struct list *head;

void init(void) {
	head=(struct list *) malloc(sizeof *head);
	head->next = NULL;
}

struct list *append(int v) {
	struct list *ptr;
	struct list *t;
	ptr=head;
	while (ptr->next != NULL) ptr = ptr->next;
	t=(struct list *) malloc(sizeof *t);
	t->value=v;
	t->next = NULL;
	ptr->next = t;
	return ptr;
	
}

struct list *insert(int v, struct list *ptr) {
	struct list *t;
	t=(struct list *) malloc(sizeof *t);
	t->value=v;
	t->next = NULL;
	ptr->next = t;
	return ptr;
	}	
	
void delete(struct list *ptr) {
	struct list *t;
	t = ptr->next;
	ptr->next = ptr->next->next;
	free(t);
	}
	


int main () {
struct list *ptr;
init();
ptr=append(1);
ptr=append(2);
ptr=append(3);
ptr=append(4);
ptr=append(5);

ptr=insert(6, ptr);
delete(ptr);


ptr=head->next;
while (ptr != NULL) {
	printf("%d\n",ptr->value);
	ptr = ptr->next;
	}



}	 

#include <stdio.h>
#include <stdlib.h>


struct node {
	int value;
	struct node *next;
	};

struct node *head;
struct node *tail;

init(void) {
	head=(struct node *) malloc(sizeof *head);
	tail=(struct node *) malloc(sizeof *head);
	head->next = tail; tail->next = tail;
}

push(int v) {
	struct node *t;
	t=(struct node *) malloc(sizeof *t);
	t->value=v;
	t->next = head->next;
	head->next = t;
}

int pop() {
	struct node *t;
	int v;
	t = head->next;
	head->next = t->next;
	v = t->value;
	free(t);
	return v;
	}	
	

int main () {
struct node *ptr;
int v;

init();

push(10);
push(20);
push(30);
push(40);
push(50);

v=pop();
printf("v=%d\n",v);
v=pop();
printf("v=%d\n",v);

ptr=head->next;
while (ptr != tail) {
        printf("%d\n",ptr->value);
        ptr = ptr->next;
        }

}

#include <stdio.h>
#include <stdlib.h>

typedef int *data_t;


struct node {
	data_t value;
	struct node *next;
	};

struct node *head;
struct node *tail;

init(void) {
	head=(struct node *) malloc(sizeof *head);
	tail=(struct node *) malloc(sizeof *head);
	head->next = tail; tail->next = tail;
}

push(data_t v) {
	struct node *t;
	t=(struct node *) malloc(sizeof *t);
	t->value=v;
	t->next = head->next;
	head->next = t;
	
	printf("inside a=%d\n",v->a);
	printf("inside value->a=%d\n",t->value->a);
	
}

data_t pop() {
	struct node *t;
	data_t v;
	t = head->next;
	head->next = t->next;
	v = t->value;
	free(t);
	return v;
	}	
	

int main () {
struct node *ptr;
data_t *x;
data_t v;

printf("xxxxx\n");

x.a=1;
x.b=2;
v=&x;

printf("outside a=%d\n",v->a);
printf("outside b=%d\n",v->b);

printf("yyyyy\n");

init();

push(v);


v=pop();
printf("v=%d\n",v);
v=pop();
printf("v=%d\n",v);

ptr=head->next;
while (ptr != tail) {
        printf("%d\n",ptr->value);
        ptr = ptr->next;
        }

}

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;

class Node {
  friend class List;

private:
	data_t value;
	Node *next;
	//constructor
	Node(const Node *n, data_t v) : next((Node *)n), value(v) {}
  	
	// default constructor
  	// (should not be available, so do not define this function)
  	Node(void);	
	
	//destructor
	~Node(void) {}
	};


class List {
private:
	Node *head;
	Node *tail;
	Node *curr;
	
public:
	List() {
	head->next = tail;
	tail->next = tail;
	}
	~List(void) {}

void push(data_t v) {
	curr = new Node(head->next, v);
	head->next = curr;
	}

data_t pop(void) {
	data_t v;
	curr = head->next;
	head->next = curr->next;
	v = curr->value;
	delete curr;
	return v;
	}	
};	

void main () {
List stack;
data_t v;
stack.push(v);

v=stack.pop();

//printf("v=%d\n",v);
v=stack.pop();
//printf("v=%d\n",v);


}

#include <stdio.h>
#include <stdlib.h>


class Node {
  friend class List;

private:
	int value;
	Node *next;
	//constructor
	Node(const Node *n, int v) : next((Node *)n), value(v) {}
  	
	// default constructor
  	// (should not be available, so do not define this function)
  	Node(void);	
	
	//destructor
	~Node(void) {}
	};


class List {
private:
	Node *head;
	Node *tail;
	Node *curr;
	
public:
	//constructor
	List() : head(0), tail(0), curr(0){
	//head->next = tail;
	//tail->next = tail;
	}
	//destructor
	~List(void) {}

void push(int v) {
	curr = new Node(head->next, v);
	head->next = curr;
	}

int pop(void) {
	int v;
	curr = head->next;
	head->next = curr->next;
	v = curr->value;
	delete curr;
	return v;
	}	
};	

void main () {
List stack;
int v;
stack.push(v);

v=stack.pop();

//printf("v=%d\n",v);
//v=stack.pop();
//printf("v=%d\n",v);


}