Skip to content

Instantly share code, notes, and snippets.

@ArnonEilat
Created January 6, 2013 23:49
Show Gist options
  • Save ArnonEilat/4471119 to your computer and use it in GitHub Desktop.
Save ArnonEilat/4471119 to your computer and use it in GitHub Desktop.
Simple C implementation of linked list with pointer to the first node and pointer the last node. Usage example included.
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int info;
} DATA;
typedef struct node {
DATA data;
struct node * prev;
struct node * next;
} NODE;
typedef struct linked_list {
NODE * first;
NODE * last;
} linked_list;
/* The following function initializes the linked list by putting zeros into the pointers containing the first and last links of the linked list. */
void linked_list_init(linked_list * list) {
list->first = 0;
list->last = 0;
}
/* Return True if list is empty*/
int isEmpty(linked_list * list) {
return (list->first == NULL);
}
/* The following function adds a new link to the end of the linked list. It allocates memory for it. The contents of the link are copied from "data". */
void linked_list_add(linked_list * list, DATA data) {
NODE * node;
/* calloc sets the "next" field to zero. */
node = calloc(1, sizeof (NODE));
if (!node) {
printf("calloc failed.\n");
exit(EXIT_FAILURE);
}
node->data = data;
if (list->last != NULL) {
/* Join the two final links together. */
node->prev = list->last;
list->last->next = node;
list->last = node;
} else {
list->first = node;
list->last = node;
}
}
void delete_NODE(linked_list * list, NODE * node) {
NODE * prev;
NODE * next;
if (isEmpty(list)) {
return;
}
prev = node->prev;
next = node->next;
if (prev != NULL) {
if (next != NULL) {
/* Both the previous and next links are valid, so just bypass "link" without altering "list" at all. */
prev->next = next;
next->prev = prev;
} else {
/* Only the previous link is valid, so "prev" is now the last link in "list". */
prev->next = 0;
list->last = prev;
}
} else {
if (next != NULL) {
/* Only the next link is valid, not the previous one, so "next" is now the first link in "list". */
next->prev = 0;
list->first = next;
} else {
/* Neither previous nor next links are valid, so the list is now empty. */
list->first = 0;
list->last = 0;
}
}
free(node);
}
void delete(linked_list * list, DATA data) {
NODE * node;
if (isEmpty(list)) {
return;
}
for (node = list->first; (node != NULL) && (node->data.info != data.info); node = node->next) {
}
if (node == NULL) {
printf("%d wasn't found.\nCannot Delete it.\n", data.info);
return;
}
delete_NODE(list, node);
return;
}
void traverse(linked_list * list) {
NODE * node;
for (node = list->first; node; node = node->next) {
printf(" %d ", node->data.info);
}
}
void traverse_in_reverse(linked_list * list) {
NODE * node;
for (node = list->last; node; node = node->prev) {
printf(" %d ", node->data.info);
}
}
/* Free the list's memory. */
void free_list(linked_list * list) {
NODE * node;
NODE * next;
for (node = list->first; node; node = next) {
/* Store the next value so that we don't access freed memory. */
next = node->next;
free(node);
}
linked_list_init(list);
}
int main() {
linked_list list;
DATA data;
NODE *node;
linked_list_init(& list);
data.info = 0;
linked_list_add(& list, data);
data.info = 1;
linked_list_add(& list, data);
data.info = 2;
linked_list_add(& list, data);
data.info = 3;
linked_list_add(& list, data);
printf("Print In Revers Order:\n\t");
traverse_in_reverse(&list);
printf("\nPrint In Regular Order:\n\t");
traverse(& list);
printf("\nDelete 1 From The List:\n\t");
data.info = 1;
delete(&list, data);
traverse(& list);
printf("\nDelete NODE From The List:\n\t");
node = list.first->next;
delete_NODE(&list, node);
traverse(&list);
free_list(&list);
return (EXIT_SUCCESS);
}
@dhtzl
Copy link

dhtzl commented May 11, 2019

101 C++ 5000 102 Java 1000 103 php 6000

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment