Singly LinkedList.c, C (gcc)

Language: Layout:

/*
 * linkedList.c
 *
 *  Created on: 22.05.2017
 *      Author: Jasper Reichardt
 */

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

/********** GLOBALS *******************************/
#define OK 0
#define ERROR -1

/********** STRUCT AND TYPES DEFINTIONS ***********/
/* a node with key, data and reference to next node*/
typedef struct Node {
	int key;
	char string[1024];
	struct Node *next;  // pointer to next node
} Node;

/* the actual linked list: ref to first and last Node, size attribute */
typedef struct LinkedList {
	struct Node *first;
	struct Node *last;
	int size;
} LinkedList;

/********** FUNCTION HEADERS **********************/
LinkedList* init_list();
void insert_end(LinkedList *list, int key, char string[]);
void insert_beginning(LinkedList *list, int key, char string[]);
int remove_end(LinkedList *list);
int remove_beginning(LinkedList *list);
int print_list(LinkedList *list);
void free_list(LinkedList *list);
char * get_string(LinkedList *list, int key);

/*********** FUNCTION DEFINITIONS ***************/

/**
 * init_list Returns an appropriately (for an empty list) initialized struct List
 *
 * @return LinkedList * 		..ptr to the newly initialized list
 */
LinkedList * init_list() {
	printf("initializing list...\n");

LinkedList *list = (LinkedList*) malloc(sizeof(LinkedList));

list->first = NULL;
	list->last = NULL;
	list->size = 0;

return list;
}

/**
 * Given a List, a key and a string adds a Node containing this
 * information at the end of the list
 *
 * @param list		LinkedList *    ..ptr to LinkedList
 * @param key       int				.. key of the Node to be inserted
 * @param string    char[]			.. the string of the Node to be inserted
 */
void insert_end(LinkedList *list, int key, char string[]) {
	printf("----------------------\n");

list->size++;                    // increment size of list

// intialize the new Node
	Node* newN = (Node*) malloc(sizeof(Node));
	newN->key = key;
	strcpy(newN->string, string);
	newN->next = NULL;

Node* oldLast = list->last;      // get the old last
	oldLast->next = newN;          // make new Node the next Node for oldlast
	list->last = newN;              // set the new last  in the list

printf("new Node(%p) at end: %d '%s' %p \n", newN, newN->key, newN->string,newN->next);
}

/**
 * Given a List, a key and a string adds a Node, containing
 * this information at the beginning of the list
 *
 * @param list		LinkedList *    ..ptr to LinkedList
 * @param key		int				.. key of the Node to be inserted
 * @param string	char[]			.. the string of the Node to be inserted
 */
void insert_beginning(LinkedList *list, int key, char string[]) {
	printf("----------------------\n");

list->size++;                    // increment size of list
	Node* oldFirst = list->first;    //get the old first node

/* intialize the new Node */
	Node* newN = (Node*) malloc(sizeof(Node));
	newN->key = key;
	strcpy(newN->string, string);
	newN->next = oldFirst;

list->first = newN;              // set the new first

/* special case: if list size == 1, then this new one is also the last one */
	if (list->size == 1)
		list->last = newN;

printf("new Node(%p) at beginning: %d '%s' %p \n", newN, newN->key,newN->string, newN->next);
}

/**
 * Removes the first Node from the list
 *
 * @param list		LinkedList *		.. ptr to the List
 *
 * @return OK | ERROR
 */
int remove_beginning(LinkedList *list) {
	printf("----------------------\n");

if (list->size <= 0)
		return ERROR;

list->size--;

Node * oldFirst = list->first;

printf("delete Node(%p) at beginning: '%d' '%s' '%p' \n", oldFirst,oldFirst->key, oldFirst->string, oldFirst->next);

free(list->first); 			//free it
	list->first = oldFirst->next;
	oldFirst = NULL;

return OK;
}

/**
 * Removes the last Node from the list.
 *
 * @param list		LinkedList *		.. ptr to the List
 *
 * @return OK | ERROR
 */
int remove_end(LinkedList *list) {
	printf("----------------------\n");

/* special case #1 */
	if (list->size <= 0)
		return ERROR;

/* special case #2 */
	if (list->size == 1) {
		free(list->first);
		list->first = NULL;
		list->last = NULL;
		return OK;
	}

printf("delete Node(%p) at end: '%d' '%s' '%p' \n", list->last,list->last->key, list->last->string, list->last->next);

list->size--;           // decrement list size
	Node * startNode = list->first;

/* find the new last node (the one before the old last one); list->size >= 2 at this point!*/
	Node * newLast = startNode;
	while (newLast->next->next != NULL) {
		newLast = newLast->next;
	}

free(newLast->next); 	//free it
	newLast->next = NULL;  	//set to NULL to denote new end of list
	list->last = newLast; 	// set the new list->last

return OK;
}

/**
 * Given a List prints all key/string pairs contained in the list to
 * the screen
 *
 * @param list		LinkedList *		.. ptr to the List
 *
 * @return	OK | ERROR
 */
int print_list(LinkedList *list) {

printf("----------------------\n");

if (list->size <= 0)
		return ERROR;

printf("List.size = %d \n", list->size);

Node *startN = list->first;  //get first

/* iterate through list and print contents */
	do {
		printf("Node#%d.string = '%s', .next = '%p' \n", startN->key,startN->string, startN->next);
		startN = startN->next;
	} while (startN != NULL);

return OK;
}

/**
 * Given a List, frees all memory associated with this list.
 *
 * @param list		LinkedList *		..ptr to the list
 */
void free_list(LinkedList *list) {
	printf("----------------------\n");
	printf("freeing list...\n");

if (list != NULL && list->size > 0) {
		Node * startN = list->first;
		Node * temp = list->first;

do {
			free(temp);
			startN = startN->next;
			temp = startN;
		} while (startN != NULL);

free(list);
	}
}

/**
 * Given a List and a key, iterates through the whole List and returns
 * the string of the first node which contains the key
 *
 * @param list		LinkedList *		..ptr to the list
 * @param key		int					.. the key of the Node to get the String from
 *
 * @return OK | ERROR
 */
char * get_string(LinkedList *list, int key) {
	printf("----------------------\n");

Node *startN = list->first;  //get first

/* if only one node.. */
	if(list->size == 1)
		return startN->string;
    
	/* iterate through list and find Node where node->key == key */
	while (startN->next != NULL) {
		if (startN->key == key)
			return startN->string;
		else
			startN = startN->next;
	}

return NULL;
}

/*************** MAIN **************/
int main(void) {

LinkedList *list = init_list();

insert_beginning(list, 1, "im the first");
	insert_end(list, 2, "im the second");
	insert_end(list, 3, "im the third");
	insert_end(list, 4, "forth here");

print_list(list);
	remove_end(list);
	print_list(list);
	remove_beginning(list);
	print_list(list);
	remove_end(list);
	print_list(list);
	printf("string at node with key %d = '%s' \n",2,get_string(list, 2));
	free_list(list);

return OK;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 0.12 sec, absolute running time: 0.14 sec, cpu time: 0 sec, memory peak: 3 Mb, absolute service time: 0,31 sec