double linked list

**cooper1200** · 06-01-2019

here is my example of double linked list

Code:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next, *previous;
}Node;

typedef struct LinkedList
{
    struct Node *head, *tail;
}LinkedList;

void createhead(LinkedList *list);
int getdata(void);
Node *getmemory(void);
void appendlist(LinkedList *list);
void prependlist(LinkedList *list);
void printlist(const LinkedList list);
void reverseprintlist(const LinkedList list);
int countnodes(const LinkedList list);
void deletelist(LinkedList *list);
void removenode(LinkedList *list);
Node *findnode(LinkedList **list);

int main()
{
    LinkedList list;

    createhead(&list);
    appendlist(&list);
    appendlist(&list);
    appendlist(&list);
    printlist(list);
    prependlist(&list);
    prependlist(&list);
    printlist(list);
    reverseprintlist(list);
    removenode(&list);
    prependlist(&list);
    appendlist(&list);
    printlist(list);
    deletelist(&list);

    return 0;
}

void createhead(LinkedList *list)
{
    Node *tmp_node = NULL;

    list->head = NULL;
    list->tail = NULL;

    tmp_node = getmemory();
    if (!tmp_node)
    {
        printf("error getting memory");
        exit(EXIT_FAILURE);
    }

    tmp_node->data = getdata();
    tmp_node->previous = NULL;
    tmp_node->next = NULL;
    list->head = tmp_node;
    list->tail = list->head;
}

int getdata(void)
{
    int data;

    printf("Please enter a number: ");
    scanf(" %d", &data);

    return data;
}

Node *getmemory(void)
{
    return malloc(sizeof(Node));
}

void appendlist(LinkedList *list)
{
    Node *tmp_node = NULL;

    tmp_node = getmemory();

    if (!tmp_node)
    {
        printf("error getting memory");
        return;
    }

    tmp_node->data = getdata();
    tmp_node->next = NULL;
    tmp_node->previous = list->tail;
    list->tail->next = tmp_node;
    list->tail = tmp_node;
    if (!list->head->next)
    {
        list->head->next = tmp_node;
    }
}

void printlist(const LinkedList list)
{
    int count = 1;
    Node *current_node = list.head;

    while (current_node)
    {
        printf("node %d's data is %d\n", count, current_node->data);
        count++;
        current_node = current_node->next;
    }
}

void deletelist(LinkedList *list)
{
    int count = 1;
    Node *tmp_node = NULL;

    while (list->head)
    {
        tmp_node = list->head->next;
        free(list->head);
        printf("node %d freed\n", count);
        count++;
        list->head = tmp_node;
    }
}

void prependlist(LinkedList *list)
{
    Node *tmp_node = NULL;

    tmp_node = getmemory();
    if (!tmp_node)
    {
        printf("error getting memory");
        return;
    }
    tmp_node->data = getdata();
    tmp_node->next = list->head;
    list->head->previous = tmp_node;
    list->head = tmp_node;
}

void reverseprintlist(const LinkedList list)
{
    int count = countnodes(list);
    Node *current_node = list.tail;

    printf("\nprinting list in reverse\n");
    while (current_node)
    {
        printf("node %d's data is %d\n", count , current_node->data);
        count--;
        current_node = current_node->previous;
    }
}

int countnodes(const LinkedList list)
{
    int count = 0;
    Node *current_node = list.head;

    while (current_node)
    {
        count++;
        current_node = current_node->next;
    }
    return count;
}

void removenode(LinkedList *list)
{
    Node *tmp_node = NULL;

    tmp_node = findnode(&list);
    if (!tmp_node) //node not found
    {
        printf("Invalid data entered data not found\n");
        return;
    }

    if (!tmp_node->previous) //node is list head
    {
        list->head = tmp_node->next;
        list->head->previous = NULL;
        tmp_node->next = NULL;
        free(tmp_node);
        return;
    }

    if (!tmp_node->next) //node is list tail
    {
        tmp_node->previous->next = NULL;
        list->tail = tmp_node->previous;
        tmp_node->previous = NULL;
        free(tmp_node);
        return;
    }
    tmp_node->previous->next = tmp_node->next;
    tmp_node->next->previous = tmp_node->previous;
    tmp_node->next = NULL;
    tmp_node->previous = NULL;
    free(tmp_node);
}

Node *findnode(LinkedList **list)
{
    int data;
    Node *current_node = (*list)->head, *tmp_node = NULL;

    printf("please enter the data to delete: ");
    scanf(" %d", &data);

    while (current_node)
    {
            if (current_node->data == data)
            {
                tmp_node = current_node;
                return tmp_node;
            }
            current_node = current_node->next;
    }
    return tmp_node;
}

any comments or criticisms welcome
coop

**laserlight** · 06-01-2019

LinkedList only has two pointers, so it is cheap to copy, hence a LinkedList parameter is okay. On the other hand, most of the functions that make up your LinkedList interface have a LinkedList* parameter, so perhaps changing printlist, reverseprintlist, and countnodes to have a const LinkedList* parameter would be more consistent.
Why does findnode need a LinkedList** parameter? It doesn't change a LinkedList*, and finding a node shouldn't even need to change the linked list, so it seems to me that it should only need a const LinkedList* parameter.
Presently, your interface for using a doubly linked list is tightly coupled with the actual use of the linked list. For example, instead of returning false or an error code, removenode prints an error message to standard output when the node is not found. This means that if I will have to go through hoops if I want to convey an error message differently, or perhaps I am willing to ignore the error for some special reason. Likewise, findnode performs interactive I/O: what if I wanted to use your doubly linked list library for a GUI? Also, findnode's printf asks "please enter the data to delete", but what if I just want to find the node in order to do something else? Rather, I would write findnode like this:
Code:
```
Node *findnode(const LinkedList *list, int data)
{
    Node *current_node = list->head;
    while (current_node)
    {
        if (current_node->data == data)
        {
            return current_node;
        }
        current_node = current_node->next;
    }
    return NULL;
}
```
Similiarly, createhead, appendlist, and prependlist should not call getdata, but rather have a parameter for the data. The code that calls them will then call getdata and pass the data to them.

**cooper1200** · 06-01-2019

i guess i really don't get the purpose of a function. to me all main should worry about is calling the outside function for example appendlist. what append list does to get the data main doesn't care about. where as if i rewrite append list to take in the data as a parameter main first has to call getdata to get the data (number) then pass it onto appendlist. Surely this ties it all up even tighter.

im not arguing with your comments im just not quite sure why
coop

**laserlight** · 06-01-2019

Originally Posted by cooper1200

i guess i really don't get the purpose of a function. to me all main should worry about is calling the outside function for example appendlist. what append list does to get the data main doesn't care about. where as if i rewrite append list to take in the data as a parameter main first has to call getdata to get the data (number) then pass it onto appendlist. Surely this ties it all up even tighter.

The idea is to divide your program into two layers:

Doubly linked list library to make it easy to work with doubly linked lists
Code that uses the doubly linked list library to provide functionality to the user of the program

This way, the second layer can easily be changed without having to change the first layer. Hence, you can reuse the same library for multiple projects, and these projects don't have to do interactive I/O in exactly the same way as you're doing with your program right now: they could read the linked list data from a file, obtain the data from the user via a GUI, randomly generate the data, etc.

Furthermore, you can more easily test your library: you can write automated unit tests that initialise the linked list with some pre-determined data, then call the various library functions and see if the result is as expected. While there are ways by which you could automate interactive I/O for testing, it would be more difficult.

So yes, the main function would "drive" the second layer, but the second layer should still be loosely coupled from the first layer, i.e., the doubly linked list library should not be (directly) calling functions that do I/O specific to your particular end-user program.

EDIT:
If you want to print error output from your library, fprintf to stderr instead of using printf to print to stdout. This way, a program using your library can be run with such errors logged to file instead of printed to screen (although again, it may be better to return a boolean value or an error code, or if applicable, a null pointer, instead of printing error output from a library). If you want to print error output to standard output from your code that uses the library as part of interactive I/O, go ahead, although if it isn't interactive I/O, you may still want to consider printing to standard error.

**cooper1200** · 06-01-2019

to be thick and clarify. how the data is obtained is nothing to do with the list functions?

**laserlight** · 06-01-2019

Originally Posted by cooper1200

how the data is obtained is nothing to do with the list functions?

Yes. If you make your linked list functions be concerned with how your data is obtained, then for each and every possible variation on obtaining the data, you must create an entirely new linked list library. That means your library is not very reusable.

(You could use callback functions to make your library more reusable, but that also makes your library more complex. It's simple and cheap to pass an integer as an argument, whereas passing a callback function pointer is more complex and may incur function call overhead.)

**cooper1200** · 06-01-2019

here is my second attempt trying to implement Laserlight's suggestions

Code:

#include <stdio.h>
#include <stdlib.h>

enum Errorcode {CREATELISTFAIL = 1, CREATENODEFAIL, NODENOTFOUND};

typedef struct Node
{
    int part_num;
    struct Node *next, *previous;
}Node;

typedef struct Linkedlist
{
    struct Node *head, *tail;
}Linkedlist;

//functions for i/o
int getinput(char str[]);
void printerror(int code);

//lined list functions
int initalizelist(Linkedlist *list, int part_num);
Node *createnode(void);
int appendlist(Linkedlist **list, int part_num);
int prependlist(Linkedlist **list, int part_num);
void printlist(const Linkedlist *list);
void reverseprintlist(const Linkedlist *list);
void printlistfrom(const Linkedlist *list, int part_num);
void deletelist(Linkedlist *list);
Node *findnode(const Linkedlist *list, int part_num);
int countnodes(const Linkedlist *list);
void removenode(Linkedlist **list, int part_num);

//extra functions
void addtofront(Linkedlist *list);
void addtoend(Linkedlist *list);
void printfrom(const Linkedlist *list);
void removenodefromlist(Linkedlist *list);

int main()
{
    int part_num, error_num;
    char strenter[] = "Please enter the part number: ";
    Linkedlist list;

    part_num = getinput(strenter);
    error_num = initalizelist(&list, part_num);
    if (error_num)
    {
        printerror(error_num);
    }
    addtoend(&list);
    addtoend(&list);
    addtofront(&list);
    addtofront(&list);
    printlist(&list);
    reverseprintlist(&list);
    printfrom(&list);
    removenodefromlist(&list);
    addtoend(&list);
    addtofront(&list);
    printlist(&list);
    deletelist(&list);

    return 0;
}

int getinput(char str[])
{
    int data;

    printf("%s", str);
    scanf(" %d", &data);

    return data;
}

void printerror(int code)
{
    switch (code)
    {
        case CREATELISTFAIL:
            fprintf(stderr, "error creating list\n");
            exit(EXIT_FAILURE);

        case CREATENODEFAIL:
            fprintf(stderr, "error creating node\n");
            return;

        case NODENOTFOUND:
            fprintf(stderr, "data not found\n");
            return;
    }
}

int initalizelist(Linkedlist *list, int part_num)
{
    list->head = NULL;
    list->tail= NULL;

    list->head = createnode();
    if (!list->head)
    {
        return CREATELISTFAIL;
    }
    list->head->part_num = part_num;
    list->head->next = NULL;
    list->head->previous = NULL;
    list->tail = list->head;

    return 0;
}

Node *createnode(void)
{
    return malloc(sizeof(Node));
}

int appendlist(Linkedlist **list, int part_num)
{
    Node *tmp_node = createnode();

    if (!tmp_node)
    {
        return CREATENODEFAIL;
    }

    tmp_node->part_num = part_num;
    tmp_node->next = NULL;

    if (!(*list)->head->next)
    {
        tmp_node->previous = (*list)->head;
        (*list)->head->next = tmp_node;
        (*list)->tail = tmp_node;
        return 0;
    }

    tmp_node->previous = (*list)->tail;
    (*list)->tail->next = tmp_node;
    (*list)->tail = tmp_node;

    return 0;
}

int prependlist(Linkedlist **list, int part_num)
{
    Node *tmp_node = createnode();

    if (!tmp_node)
    {
        return CREATENODEFAIL;
    }

    tmp_node->part_num = part_num;
    tmp_node->next = (*list)->head;
    (*list)->head->previous = tmp_node;
    (*list)->head = tmp_node;

    return 0;
}

void printlist(const Linkedlist *list)
{
    int count = 1;
    Node *current_node = list->head;

    while (current_node)
    {
        printf("node %d's part number is %d\n", count, current_node->part_num);
        count++;
        current_node = current_node->next;
    }
}

void reverseprintlist(const Linkedlist *list)
{
    int count = countnodes(list);
    Node *current_node = list->tail;

    printf("\nreverse print list\n");
    while (current_node)
    {
        printf("node %d's part number is %d\n", count, current_node->part_num);
        count--;
        current_node = current_node->previous;
    }
}

void printlistfrom(const Linkedlist *list, int part_num)
{
    int count = 1;
    Node *current_node = findnode(list, part_num);

    printf("printing nodes from %d as node 1\n", current_node->part_num);

    while (current_node)
    {
        printf("node %d's part number is %d\n", count, current_node->part_num);
        count++;
        current_node = current_node->next;
    }
}
void deletelist(Linkedlist *list)
{
    int count = 1;
    Node *current = list->head, *tmp_node = NULL;

    while (current)
    {
        tmp_node = current->next;
        printf("freeing node %d\n", count);
        free(current);
        current = tmp_node;
        count++;
    }
}

Node *findnode(const Linkedlist *list, int part_num)
{
    Node *current_node = list->head;

    while (current_node)
    {
        if (current_node->part_num == part_num)
        {
            return current_node;
        }
        current_node = current_node->next;
    }

    return NULL;
}

int countnodes(const Linkedlist *list)
{
    int count = 0;
    Node *current_node = list->head;

    while (current_node)
    {
        count++;
        current_node = current_node->next;
    }

    return count;
}

void removenode(Linkedlist **list, int part_num)
{
    Node *tmp_node = findnode(*list, part_num);

    if (!tmp_node->previous)
    {
        (*list)->head = (*list)->head->next;
        (*list)->head->previous = NULL;
        tmp_node->next = NULL;
        free(tmp_node);
        return;
    }

    if (!tmp_node->next)
    {
        tmp_node->previous->next = NULL;
        (*list)->tail = tmp_node->previous;
        tmp_node->previous = NULL;
        free(tmp_node);
        return;
    }

    tmp_node->previous->next = tmp_node->next;
    tmp_node->next->previous = tmp_node->previous;
    tmp_node->next = NULL;
    tmp_node->previous = NULL;
    free(tmp_node);
}

void addtofront(Linkedlist *list)
{
    int part_num, error_num;
    char strenter[] = "Please enter the part number: ";

    part_num = getinput(strenter);
    error_num = prependlist(&list, part_num);
    if (error_num)
    {
        printerror(error_num);
    }
}

void addtoend(Linkedlist *list)
{
    int part_num, error_num;
    char strenter[] = "Please enter the part number: ";

    part_num = getinput(strenter);
    error_num = appendlist(&list, part_num);
    if (error_num)
    {
        printerror(error_num);
    }
}

void printfrom(const Linkedlist *list)
{
    int part_num;
    char strpart[] = "Please enter the part number you wish to print from: ";
    Node *tmp_node;

    part_num = getinput(strpart);
    tmp_node = findnode(list, part_num);
    if (!tmp_node)
    {
        printerror(NODENOTFOUND);
        return;
    }
    printlistfrom(list, part_num);
}

void removenodefromlist(Linkedlist *list)
{
    int part_num;
    char strremove[] = "Please enter the part number you wish to remove: ";
    Node *tmp_node;

    part_num = getinput(strremove);
    tmp_node = findnode(list, part_num);
    if (!tmp_node)
    {
        printerror(NODENOTFOUND);
        return;
    }
    removenode(&list, part_num);
}

comments/criticisms welcome

**laserlight** · 06-02-2019

Your error code naming sucks: use underscores to separate words, e.g., CREATE_NODE_FAIL instead of CREATENODEFAIL.

I would write initializelist like this:

Code:

int LinkedList_initalize(Linkedlist *list)
{
    list->head = NULL;
    list->tail= NULL;
}

You're initialising the linked list, not creating a linked list with one element. If not, then it would be impossible to have an empty linked list.

I would write the append and prepend functions like this:

Code:

int LinkedList_append(Linkedlist *list, int data)
{
    Node *node = malloc(sizeof(*node));
    if (!node)
    {
        return CREATENODEFAIL;
    }
    node->data = data;
    node->next = NULL;

    if (list->tail)
    {
        node->previous = list->tail;
        list->tail->next = node;
        list->tail = node;
    }
    else
    {
        node->previous = NULL;
        list->head = node;
        list->tail = node;
    }
    return 0;
}

int LinkedList_prepend(Linkedlist *list, int data)
{
    Node *node = malloc(sizeof(*node));
    if (!node)
    {
        return CREATENODEFAIL;
    }
    node->data = data;
    node->previous = NULL;

    if (list->head)
    {
        node->next = list->head
        list->head->previous = node;
        list->head = node;
    }
    else
    {
        node->next = NULL;
        list->head = node;
        list->tail = node;
    }
    return 0;
}

There is no reason why these functions should have a LinkedList** parameter. A LinkedList* parameter will do. If you're going with named error codes, then you should have a named result code of 0 rather than returning 0 directly. I ditched createnode because it doesn't really add value over a simple malloc call.

What's with "part_num" anyway?

I would write the function to delete the linked list like this:

Code:

void LinkedList_destroy(Linkedlist *list)
{
    Node *current = list->head;
    while (current)
    {
        Node *next = current->next;
        free(current);
        current = next;
    }
    list->head = NULL;
    list->tail = NULL;
}

Notice that I don't print anything from it.

There is no reason why removenode should have a LinkedList** parameter. A LinkedList* parameter will do.

**cooper1200** · 06-02-2019

printing from deleate list is so i can see its all deleted correctly. the double pointers are there because i needed an interface to the linked list functions rather than having main 1000 yards long full of if statements for every little thing create node was there so i didn't have to type malloc(sizeof(Node)) in every function

**cooper1200** · 06-02-2019

lines 11 to 15 of your suggestions what happens if the tail is the head how does head->next know where to go

**laserlight** · 06-02-2019

Originally Posted by cooper1200

the double pointers are there because i needed an interface to the linked list functions rather than having main 1000 yards long full of if statements for every little thing

What do you mean? All they are doing is making you do more work: you have to dereference the pointer in the function, and when calling the function from another function that already has a linked list pointer, you have to take the address of that pointer.

Originally Posted by cooper1200

what happens if the tail is the head how does head->next know where to go

That's done on line 14. head->next is set to node.

**cooper1200** · 06-02-2019

ok im either looking at a different version of the code or im not getting this.

you have 2 pointers head and tail
each of those pointers have 2 pointers next and previous
head->next is null and tail->next is null.
you then set the tail next to point at the new node (line 14)
surely head->next is still null

**cooper1200** · 06-02-2019

to change the list in anyway i need the address of list yes? or at least the address of the head and tail nodes (which list contains) if i have a single pointer to list then don't pass the address of list any function called from with in is going to be passed the address of the pointer not list isn't it?

**cooper1200** · 06-02-2019

i just tried it. and it worked (im sure your not surprised)
can anyone recommend a book or tutorial on pointers and how they work because im just not getting it. sometimes you just need the variable sometimes you need the address and sometimes you need a pointer to a pointer and all im doing is frustrating myself and everyone that tries to help me.
coop

**laserlight** · 06-02-2019

Originally Posted by cooper1200

each of those pointers have 2 pointers next and previous

No, they don't. Pointers don't have next and previous pointers. Node objects have next and previous pointers. So, the two pointers point to the same Node object, and that single Node object has a next pointer and a previous pointer. Hence, if you change the next pointer of that Node object through one of the pointers pointing to it, it will appear changed when you check it with the other pointer pointing to it.

Originally Posted by cooper1200

to change the list in anyway i need the address of list yes?

Yes, and that means a LinkedList*. You only need a LinkedList** if you want to change the pointer to the linked list, e.g., malloc the pointer to the linked list, but you're not doing that here.

Thread: double linked list

Thread Tools

Search Thread

Display

double linked list

Similar Threads

Dynamic List Char Array & Double Linked List

double linked list

single linked list to double linked list (help)

What is the use of Double Linked List?

What is double-linked list?

Tags for this Thread