201 lines
3.1 KiB
C
201 lines
3.1 KiB
C
#include <stdio.h>
|
|
#include "stdlib.h"
|
|
|
|
typedef int BOOL;
|
|
#define TRUE 1
|
|
#define FALSE 0
|
|
|
|
typedef struct node
|
|
{
|
|
int value;
|
|
struct node *next;
|
|
struct node *prev;
|
|
} Node;
|
|
|
|
typedef struct
|
|
{
|
|
int value;
|
|
BOOL flag;
|
|
} ListValue;
|
|
|
|
static Node* HEAD;
|
|
static Node* TAIL;
|
|
|
|
static int LENGTH = 0;
|
|
|
|
// O(1) operation, no growth by input
|
|
BOOL append(int value)
|
|
{
|
|
Node* new_head = malloc(sizeof(Node));
|
|
if (new_head == NULL)
|
|
return FALSE;
|
|
|
|
new_head->value = value;
|
|
new_head->prev = HEAD;
|
|
|
|
if (HEAD != NULL)
|
|
HEAD->next = new_head;
|
|
else
|
|
TAIL = new_head;
|
|
|
|
HEAD = new_head;
|
|
++LENGTH;
|
|
|
|
return TRUE;
|
|
}
|
|
|
|
// O(1) operation, no growth by input
|
|
BOOL prepend(int value)
|
|
{
|
|
Node* new_tail = malloc(sizeof(Node));
|
|
if (new_tail == NULL)
|
|
return FALSE;
|
|
|
|
new_tail->value = value;
|
|
new_tail->next = TAIL;
|
|
|
|
if (TAIL != NULL)
|
|
TAIL->prev = new_tail;
|
|
else
|
|
HEAD = new_tail;
|
|
|
|
TAIL = new_tail;
|
|
++LENGTH;
|
|
|
|
return TRUE;
|
|
}
|
|
|
|
// O(n) operation, the longer the list, the longer the search, by N in the worst case
|
|
Node* get_node(int index)
|
|
{
|
|
if (TAIL == NULL)
|
|
return NULL;
|
|
|
|
Node* iterator = TAIL;
|
|
while (index > 0 && iterator->next != NULL)
|
|
{
|
|
--index;
|
|
iterator = iterator->next;
|
|
}
|
|
|
|
if (index > 0)
|
|
return NULL;
|
|
|
|
return iterator;
|
|
}
|
|
|
|
// O(n) operation, the longer the list, the longer the search, by N in the worst case
|
|
ListValue get(int index)
|
|
{
|
|
ListValue result = { 0, FALSE };
|
|
|
|
Node* iterator = get_node(index);
|
|
if (iterator == NULL)
|
|
return result;
|
|
|
|
result.flag = TRUE;
|
|
result.value = iterator->value;
|
|
|
|
return result;
|
|
}
|
|
|
|
// O(n) operation, the longer the list, the longer the search, by N in the worst case
|
|
BOOL insert_at(int index, int value)
|
|
{
|
|
Node* iterator = get_node(index);
|
|
if (iterator == NULL)
|
|
return FALSE;
|
|
|
|
Node* new_node = malloc(sizeof(Node));
|
|
if (new_node == NULL)
|
|
return FALSE;
|
|
|
|
new_node->value = value;
|
|
new_node->next = iterator;
|
|
|
|
if (iterator->prev)
|
|
{
|
|
new_node->prev = iterator->prev;
|
|
iterator->prev->next = new_node;
|
|
}
|
|
else
|
|
TAIL = new_node;
|
|
|
|
++LENGTH;
|
|
return TRUE;
|
|
}
|
|
|
|
// O(n) operation, the longer the list, the longer the search, by N in the worst case
|
|
BOOL remove_at(int index)
|
|
{
|
|
Node* iterator = get_node(index);
|
|
if (iterator == NULL)
|
|
return FALSE;
|
|
|
|
if (HEAD != TAIL)
|
|
{
|
|
if (iterator->next)
|
|
iterator->next->prev = iterator->prev;
|
|
else
|
|
HEAD = iterator->prev;
|
|
|
|
if (iterator->prev)
|
|
iterator->prev->next = iterator->next;
|
|
else
|
|
TAIL = iterator->next;
|
|
}
|
|
else
|
|
{
|
|
HEAD = NULL;
|
|
TAIL = NULL;
|
|
}
|
|
|
|
free(iterator);
|
|
iterator = NULL;
|
|
|
|
--LENGTH;
|
|
return TRUE;
|
|
}
|
|
|
|
int main()
|
|
{
|
|
append(5);
|
|
append(22);
|
|
append(66);
|
|
prepend(122);
|
|
prepend(9);
|
|
insert_at(0, 999);
|
|
insert_at(3, 3);
|
|
|
|
Node* iterator = TAIL;
|
|
while (iterator != NULL)
|
|
{
|
|
printf("it: %d\n", iterator->value);
|
|
iterator = iterator->next;
|
|
}
|
|
|
|
printf("------\n");
|
|
|
|
remove_at(0);
|
|
remove_at(LENGTH-1);
|
|
printf("h: %d\n", HEAD->value);
|
|
printf("t: %d\n", TAIL->value);
|
|
|
|
iterator = TAIL;
|
|
while (iterator != NULL)
|
|
{
|
|
printf("it: %d\n", iterator->value);
|
|
iterator = iterator->next;
|
|
}
|
|
|
|
printf("------\n");
|
|
|
|
remove_at(1);
|
|
iterator = TAIL;
|
|
while (iterator != NULL)
|
|
{
|
|
printf("it: %d\n", iterator->value);
|
|
iterator = iterator->next;
|
|
}
|
|
}
|