148 lines
2.9 KiB
C
148 lines
2.9 KiB
C
//
|
|
// Created by lukas on 5/25/22.
|
|
//
|
|
|
|
#ifndef UNTITLED_LIST_H
|
|
#define UNTITLED_LIST_H
|
|
|
|
#include <malloc.h>
|
|
|
|
struct Node {
|
|
struct Node *next;
|
|
struct Node *prev;
|
|
void *dta;
|
|
};
|
|
typedef struct Node Node;
|
|
|
|
typedef struct {
|
|
Node *head;
|
|
unsigned length;
|
|
} List;
|
|
|
|
List *newList() {
|
|
List *list = malloc(sizeof(List));
|
|
return list;
|
|
}
|
|
|
|
Node *_newNode(Node *next, Node *prev, void *dta) {
|
|
Node *newnode = malloc(sizeof(Node));
|
|
newnode->next = next;
|
|
newnode->prev = prev;
|
|
newnode->dta = dta;
|
|
return newnode;
|
|
}
|
|
|
|
Node *_traverseToLast(Node *node) {
|
|
if (node->next != NULL) {
|
|
return _traverseToLast(node->next);
|
|
} else {
|
|
return node;
|
|
}
|
|
}
|
|
|
|
Node *_traverseToPos(Node *node, int pos) {
|
|
if (pos > 0) {
|
|
if (node->next != NULL) {
|
|
return _traverseToPos(node->next, pos - 1);
|
|
} else {
|
|
return NULL;
|
|
}
|
|
} else {
|
|
return node;
|
|
}
|
|
}
|
|
|
|
void append(List *list, void *elem) {
|
|
if (list->head == NULL) {
|
|
// create head
|
|
list->head = _newNode(NULL, NULL, elem);
|
|
} else {
|
|
// append element
|
|
Node *last = _traverseToLast(list->head);
|
|
last->next = _newNode(NULL, last, elem);
|
|
}
|
|
}
|
|
|
|
int _length(Node *node) {
|
|
if (node->next == NULL) {
|
|
return 1;
|
|
} else {
|
|
return 1 + _length(node->next);
|
|
}
|
|
}
|
|
|
|
int length(List *list) {
|
|
if (list->head == NULL) {
|
|
return 0;
|
|
}
|
|
return _length(list->head);
|
|
}
|
|
|
|
void insert(List *list, void* elem, int position) {
|
|
Node* insertpos = _traverseToPos(list->head, position);
|
|
Node* newnode = _newNode(insertpos->next, insertpos, elem);
|
|
|
|
insertpos->next = newnode;
|
|
insertpos->next->next->prev = newnode;
|
|
}
|
|
|
|
void delete(List *list, int position) {
|
|
Node *todel = _traverseToPos(list->head, position);
|
|
|
|
if (todel->prev == NULL) {
|
|
// we are the header
|
|
list->head = todel->next;
|
|
if (list->head != NULL) {
|
|
list->head->prev = NULL;
|
|
}
|
|
} else if (todel->next == NULL) {
|
|
// we are the last item
|
|
todel->prev->next = NULL;
|
|
} else {
|
|
todel->prev->next = todel->next;
|
|
todel->next->prev = todel->prev;
|
|
}
|
|
|
|
free(todel);
|
|
}
|
|
|
|
void deleteAll(List *list) {
|
|
while (list->head != NULL) {
|
|
delete(list, 0);
|
|
}
|
|
}
|
|
|
|
void deleteList(List *list) {
|
|
deleteAll(list);
|
|
free(list);
|
|
}
|
|
|
|
Node *first(List *list) {
|
|
return list->head;
|
|
}
|
|
|
|
Node *last(List *list) {
|
|
return _traverseToLast(list->head);
|
|
}
|
|
|
|
List *merge(List *list1, List *list2) {
|
|
Node* end = last(list1);
|
|
end->next = list2->head;
|
|
list2->head->prev = end;
|
|
return list1;
|
|
}
|
|
|
|
void print(List *list, char *typeFormatter) {
|
|
Node *curr = list->head;
|
|
printf("{");
|
|
while (curr != NULL) {
|
|
printf(typeFormatter, curr->dta);
|
|
printf(", ");
|
|
|
|
curr = curr->next;
|
|
}
|
|
printf("}\n");
|
|
}
|
|
|
|
#endif //UNTITLED_LIST_H
|