C++

Forum

 
 
C Programming - Doubly Linked Lists

ronnn (5)
Hello, i recently discovered this website after trying to look for some help with my assignment in C. I am having an issue where whenever I try to print my doubly linked list backwards nothing gets printed. I really have no clue whats wrong and have tried wrapping my head around this a few different ways.

anyways here the implementation requirements and my code:
To maintain the doubly-linked list, you should keep a pointer to the head node of the list (or NULL if the list is empty), and a pointer to the tail node of the list (or NULL if the list is empty). Optionally you may also keep an integer count, which indicates the current number of nodes in the list.

You should implement the following functions in mylist.c file (a template file is provided). The functions are declared in the header file mylist.h (the header file is provided and you’re not allowed to modify this file).

insert(char* str), which creates a node with the given string. Important: you should use the malloc() function twice: once to allocate the space for the node, and the other to allocate the space for copying the string (str) passed in as the argument. You should then insert the newly created node into the doubly-linked list in increasing order (using the standard strcmp() function from libc for string comparison). It’s OK to have nodes with the same string.
delete (char* str), which removes the node that has the given string. You should search for the node by following the linked list in order; once the node is found, you should reclaim the node by calling the free() function twice: once to reclaim the space occupied by the string, and the other to reclaim the node itself. If the node is not found, the operation can be simply ignored.
list(int reverse_order), which prints out all the strings stored in the linked list in order. If reverse_order is true (i.e., non-zero), print the strings from tail to head. Otherwise, print the strings from head to tail.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
  #include "mylist.h"
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>



struct node_t {
    char *str;
    struct node_t* prev;
    struct node_t* next;
};
typedef struct node_t node_t;

node_t* head = NULL;
node_t* tail = NULL;



bool isEmpty()
{
    return head == NULL;
}



void insert(char* str)
{
    
    node_t *node = (struct node_t*) malloc(sizeof(node_t));
    
    node->str = (char *) malloc(strlen(str) + 1); //populating node
    strcpy(node->str, str);
    
    
    if(isEmpty())
    {
        
        head = node;
        tail = head->next;
        printf("%s ", tail->prev->str);
    }
    else{
       
        //need to check where it goes
        node_t *behind = NULL, *sniffer; // the in-between nodes that we need
        
        for(sniffer = head; sniffer; sniffer = sniffer->next)
        {
            if(strcmp(sniffer->str, node->str) > 0){
                //printf("hey %s", sniffer->str);
                break; // sniffer is now ahead, break loop
            }
            behind = sniffer; //behind is the node we need for ->prev
        }
        if (!sniffer && behind) { // at the end INSERTING AT THE END
            node->next = NULL;
            node->prev = behind;
            behind->next = node;
            behind=node;
            
        }
        if(!behind && sniffer)  //at the beginning INSERTING AT START
            {
                node->prev = NULL;
                node->next = head;
                head->prev = node;
                head = node;
        }
        if(behind && sniffer)
        {
            behind->next = node;
            node->prev = behind;
            node->next = sniffer;
            sniffer->prev = node;
        }
}
}

void delete(char* str)
{

}

void list(int reverse_order)
{
    /*
    for(node_t *temp = head; temp; temp = temp->next)
    {
        printf("%s ", temp ->str);
    }
    printf("\n");
    */
    for(node_t *temp = tail; temp; temp = temp->prev)
    {
        printf("%s ", temp->str);
    }
    printf("\n");
}


and i have been using this main function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "mylist.h"


int main()
{
    insert("D");
    list(0);
    insert("E");
    list(0);
    insert("B");
    list(0);
    insert("A");
    insert("C");
    list(0);
    
}


Any help is greatly appreciated.
Last edited on
salem c (3700)
> node_t *node = (struct node_t*) malloc(sizeof(node_t));
Remove the cast, and compile it.
If you get a warning about not being able to convert void*, then you need to stop invoking your C++ compiler, and instead compile using a C compiler.

> node->str ...
You also need to initialise your prev/next to be NULL pointers as well.

1
2
3
 
        head = node;
        tail = head->next;
        printf("%s ", tail->prev->str);

The first node is just
head = tail = node;

With of course the above mentioned fact that the nodes next/prev are indeed NULL.

The rest looks about right.

seeplus (6597)
There's also an issue with insertion at tail - tail isn't set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

struct node_t {
	char* str;
	struct node_t* prev;
	struct node_t* next;
};
typedef struct node_t node_t;

node_t* head = NULL;
node_t* tail = NULL;

bool isEmpty()
{
	return head == NULL;
}

void insert(const char* str)
{
	node_t* const node = (struct node_t*)malloc(sizeof(node_t));

	node->str = (char*)malloc(strlen(str) + 1); //populating node
	strcpy(node->str, str);

	if (isEmpty())
	{
		head = tail = node;
	} else {
		//need to check where it goes
		node_t *behind = NULL, *sniffer; // the in-between nodes that we need

		for (sniffer = head; sniffer; sniffer = sniffer->next)
		{
			if (strcmp(sniffer->str, node->str) > 0) {
				break; // sniffer is now ahead, break loop
			}
			behind = sniffer; //behind is the node we need for ->prev
		}

		if (!sniffer && behind) { // at the end INSERTING AT THE END
			node->next = NULL;
			node->prev = behind;
			behind->next = node;
			tail = node;
		}

		if (!behind && sniffer)  //at the beginning INSERTING AT START
		{
			node->prev = NULL;
			node->next = head;
			head->prev = node;
			head = node;
		}

		if (behind && sniffer)
		{
			behind->next = node;
			node->prev = behind;
			node->next = sniffer;
			sniffer->prev = node;
		}
	}
}

/*
void delete(char* str)
{

}
*/

void list(int reverse_order)
{
	puts("forward");
	for(node_t *temp = head; temp; temp = temp->next)
	{
		printf("%s ", temp ->str);
	}
	printf("\n");

	puts("reverse");
	for (node_t* temp = tail; temp; temp = temp->prev)
	{
		printf("%s ", temp->str);
	}

	printf("\n");
}

int main()
{
	insert("D");
	list(0);
	insert("E");
	list(0);
	insert("B");
	list(0);
	insert("A");
	insert("C");
	list(0);

}


which displays:


forward
D
reverse
D
forward
D E
reverse
E D
forward
B D E
reverse
E D B
forward
A B C D E
reverse
E D C B A

ronnn (5)
thanks for your help salem and seeplus, I finally got it working! Now I can finally work on the delete function :,)
Topic archived. No new replies allowed.