Skip to content

Instantly share code, notes, and snippets.

@sewera
Created May 21, 2019 22:24
Show Gist options
  • Save sewera/2494f17088a63fd3c35fb806e0f2992c to your computer and use it in GitHub Desktop.
Save sewera/2494f17088a63fd3c35fb806e0f2992c to your computer and use it in GitHub Desktop.
Implementation of some operations in doubly linked lists in c (push back, printing, substitution)
/**
* Copyright 2019 Błażej Sewera
* Licensed under MIT License
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node* next;
struct node* prev;
} Node;
Node* push_back(Node** first_ref, Node** last_ref, int data) {
// Func inserting a node at the end of the list
Node* new = malloc(sizeof(Node)); // same as new Node(); in cpp
new->data = data;
Node* current;
if (*first_ref == NULL) {
// if the list is empty
new->next = NULL;
new->prev = NULL;
*first_ref = new;
*last_ref = new;
} else {
current = *first_ref;
// Traverse to the end of the list
while (current->next != NULL)
current = current->next;
current->next = new;
new->prev = current;
*last_ref = new;
}
return new;
}
void print_list(Node** first_ref, Node** last_ref) {
Node* current = *first_ref;
printf("List forward: [ ");
while (current != NULL) {
printf("%d, ", current->data);
current = current->next;
}
printf("]\n");
current = *last_ref;
printf("List backwards: [ ");
while (current != NULL) {
printf("%d, ", current->data);
current = current->prev;
}
printf("]\n");
}
void substitute(Node** first_ref, Node** last_ref, int n, int new_data) {
Node* current = *first_ref;
// if you have a `size` variable in list class,
// you can check for index out of range error
// before the for loop
// Also, this is some kind of
// get_node_ptr_at_index(int n)
// function, so you can use it instead
// if provided
for (int i = 0; i < n; ++i) {
if (current != NULL)
current = current->next;
else {
printf("[E] Index number out of range\n");
return;
}
}
Node* new = malloc(sizeof(Node)); // = new Node();
new->data = new_data;
new->next = current->next;
new->prev = current->prev;
if (current->prev != NULL)
current->prev->next = new;
else
*first_ref = new;
if (current->next != NULL)
current->next->prev = new;
else
*last_ref = new;
}
int main() {
Node* first = NULL;
Node* last = NULL;
push_back(&first, &last, 0);
push_back(&first, &last, 1);
push_back(&first, &last, 2);
push_back(&first, &last, 3);
push_back(&first, &last, 4);
push_back(&first, &last, 5);
print_list(&first, &last);
substitute(&first, &last, 2, 99);
substitute(&first, &last, 4, 120);
print_list(&first, &last);
substitute(&first, &last, 0, 32);
substitute(&first, &last, 5, 64);
print_list(&first, &last);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment