Skip to content

Instantly share code, notes, and snippets.

@tbnbooij

tbnbooij/list.c

Created March 13, 2018 16:07
Show Gist options
  • Save tbnbooij/663cdf836a6b77a292feff9304923a2d to your computer and use it in GitHub Desktop.
Save tbnbooij/663cdf836a6b77a292feff9304923a2d to your computer and use it in GitHub Desktop.
Download ZIP
Computation II - Lab 3 created by tbnbooij - https://repl.it/@tbnbooij/Computation-II-Lab-3
Raw
list.c
#include "list.h"
#include <stdio.h>
#include <stdbool.h>
List *List_create() {
List *list = (List *)malloc(sizeof(List));
list->counter = 0;
list->head = NULL;
return list;
}
// You still need to add the remaining function definitions, as defined in the
// tasks
void List_print(List *list) {
int i = 0;
Node *end = list->head;
while (i < list->counter) {
printf("-> id: %i\n", end->item->id);
end = end->next;
i++;
}
}
void List_append(List *list) {
Node *node = (Node *)malloc(sizeof(Node));
Item *item = (Item *)malloc(sizeof(Item));
node->item = item;
list->counter++;
item->id = list->counter;
if (list->head != NULL) {
Node *end = list->head->prev;
node->prev = end;
node->next = list->head;
end->next = node;
list->head->prev = node;
} else {
node->next = node;
node->prev = node;
list->head = node;
}
}
void List_insert(List *list) {
Node *node = (Node *)malloc(sizeof(Node));
Item *item = (Item *)malloc(sizeof(Item));
node->item = item;
list->counter++;
item->id = list->counter;
if (list->head != NULL) {
Node *second = list->head;
Node *end = list->head->prev;
node->next = second;
node->prev = second->prev;
end->next = node;
second->prev = node;
list->head = node;
} else {
node->next = node;
node->prev = node;
list->head = node;
}
}
Node *List_find(List *list, int id) {
Node *current = list->head;
if (list->head == NULL)
return NULL;
int i = 0;
while (i < list->counter) {
if (current->item->id == id) {
return current;
}
current = current->next;
i++;
}
return NULL;
}
void List_remove(List *list, Node *node) {
if (node != NULL && list->head != NULL) {
Node *prevNode = node->prev;
Node *nextNode = node->next;
prevNode->next = nextNode;
nextNode->prev = prevNode;
if (list->head == node)
list->head = nextNode;
free(node->item);
free(node);
list->counter--;
if (list->counter == 0)
list->head = NULL;
}
}
void List_destroy(List *list) {
if (list->head != NULL) {
while (list->counter != 0) {
Node *end = list->head->prev;
List_remove(list, end);
}
}
}
void List_putfirst(List *list, Node *node) {
if (node != NULL && list->counter > 1) {
Node *prevNode = node->prev;
Node *nextNode = node->next;
prevNode->next = nextNode;
nextNode->prev = prevNode;
Node *head = list->head;
Node *end = head->prev;
node->next = head;
node->prev = end;
head->prev = node;
end->next = node;
list->head = node;
}
}
void List_sort(List *list) {
// If the linked list has at least 2 items
if (list->counter > 1) {
bool still_sorting = true;
while (still_sorting) {
still_sorting = false;
// The "Compare Node" is the first node in the set of the two compared nodes
Node *cmpNode = list->head;
// As long as we haven't hit the end of the list yet
while (cmpNode->next != list->head) {
// If the cmpNode has a higher ID than the next node
if (cmpNode->item->id > cmpNode->next->item->id) {
// Then swap these two nodes
Node *swapNode = cmpNode->next;
Node *nextNode = swapNode->next;
Node *prevNode = cmpNode->prev;
swapNode->next = cmpNode;
cmpNode->prev = swapNode;
cmpNode->next = nextNode;
swapNode->prev = prevNode;
prevNode->next = swapNode;
nextNode->prev = cmpNode;
// And update the list head pointer if necessary
if (list->head == cmpNode) {
list->head = swapNode;
}
still_sorting = true;
}
// Now move the cmpNode one space to the right
cmpNode = cmpNode->next;
}
}
}
}
Raw
list.h
#ifndef _LIST_H_
#define _LIST_H_
#include<stdio.h>
#include<stdlib.h>
struct Node;
// A simple data structure that forms the core of List
typedef struct Node
{
struct Node* next;
struct Node* prev;
struct Item* item;
} Node;
typedef struct List {
int counter;
Node* head;
} List;
typedef struct Item
{
int id;
} Item;
List *List_create();
void List_destroy(List *list);
void List_clear(List *list);
void List_print(List*list);
void List_append(List *list);
void List_insert(List *list);
void List_remove(List* list, Node* node);
Node* List_find(List *list,int id);
void List_putfirst(List *list,Node* node);
void List_sort(List* list);
#endif // _LIST_H_
Raw
main.c
#include <stdio.h>
#include "list.h"
char get_command()
{
char c;
printf("Type command: ");
scanf(" %c",&c);
return c;
}
void main()
{
List* myList = List_create();
int idnumb;
printf("-------- Ring-style linked list base class by T.B.N. Booij. --------\n\n");
char command;
while ((command = get_command()) != 'q') {
switch (command) {
case 'a': // append
List_append(myList);
break;
case 'i': // insert
List_insert(myList);
break;
case 'd': // delete
printf("Which item would you like to delete: ");
scanf(" %i",&idnumb);
Node* n = List_find(myList, idnumb);
List_remove(myList, n);
break;
case 'f': // put first
printf("Which item would you like to put first: ");
scanf(" %i",&idnumb);
Node* m = List_find(myList, idnumb);
List_putfirst(myList, m);
break;
case 'p': // print
List_print(myList);
break;
case 's': // sort
List_sort(myList);
break;
case 'x': // destroy list
List_destroy(myList);
break;
case 'q':
break;
default:
printf("Command unknown!\n");
break;
}
}
printf("Bye bye!\n");
List_destroy(myList);
free(myList);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment