C code to pop element shows segmentation error when the length of the list is 1. This is my code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node
{
int data;
struct Node* next;
};
// create a node with data as x
struct Node* create_node(int x) {
struct Node* ptr = malloc(sizeof(struct Node)); //this means ptr is pointng towards Node, i.e ptr will change values of Node and space is allocated
ptr->next = NULL;
ptr->data = x;
return ptr;
}
// delete the node at `ptr` and free its memory
void delete_node(struct Node* ptr) {
free(ptr);
}
struct Node* PythonListHead = NULL;
// prints the list in space-separated format
void print_list(struct Node* head) {
struct Node* cur = head;
while(cur) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
//PythonListHead=create_node(10);
// Add an item to the end of the list
void append(int x) { //working perfectly
struct Node *cursor=PythonListHead; //cursor points to whatever PythonListHead points to
struct Node* a=create_node(x);
if (PythonListHead==NULL){
PythonListHead=create_node(x);
}
else{
while(cursor->next!=NULL){
cursor=cursor->next;
}
cursor->next=a;
}
}
/ Return the number of elements in the list
int len() { //working perfectly
// your code goes here
struct Node* last=PythonListHead;
int count=0;
while (last->next!=NULL){
count ;
last=last->next;
}
return count 1;
}
// Remove the item at the end of the list
void pop() { //working nominally (not working when length of the list is 1)
if (len()==1){
PythonListHead=NULL;
}
if (len()==2){
delete_node(PythonListHead->next);
PythonListHead->next=NULL;
}
else{
struct Node* cursor=PythonListHead;
int count=0;
while (cursor){
cursor=cursor->next;
count ;
if (count==(len()-2)){
delete_node(cursor->next);
cursor->next=NULL;
}
}
}
}
int main(int argc, char const *argv[])
{
int T;
scanf("%d", &T);
char operation_type[20];
int indices[100];
while(T--) {
scanf("%s", operation_type);
if(strcmp(operation_type, "append") == 0) {
int x;
scanf("%d", &x);
append(x);
}
if(strcmp(operation_type, "pop") == 0) {
pop();
}
if(strcmp(operation_type, "len") == 0) {
int length = len();
printf("%d\n", length);
}
if(strcmp(operation_type, "print") == 0) {
print_list(PythonListHead);
}
}
}
I have added functions to append elements and print the list. The first line of input is an integer which shows the number of commands we can enter. The output is as follows:
20
append 1
append 2
append 3
print
1 2 3
pop
print
1 2
pop
print
1
pop
Segmentation fault: 11
The interesting thing is, that when I comment out this part of pop():
if (len()!=1 || len()!=2){
struct Node* cursor=PythonListHead;
int count=0;
while (cursor){
cursor=cursor->next;
count ;
if (count==(len()-2)){
delete_node(cursor->next);
cursor->next=NULL;
}
}
}
...Or add a return statement:
if (len()==1){
PythonListHead=NULL;
return;
}
The code works perfectly again for a list with length one. Why's this happening? It shouldn't go into the third block else{} at all, and even if it does it will terminate because the while condition will not be fulfilled. That's what I understand from my experience with Python, I don't fully understand how C compiles.
CodePudding user response：
Your len function has a bug. If you think of an empty list, then this:
int len() {
struct Node* last=PythonListHead;
while (last->next!=NULL) { // if last == NULL, **boom**
... will dereference a NULL pointer. Fix:
int len() {
int count = 0;
for(struct Node* last = PythonListHead; last; last = last->next) {
count ;
}
return count;
}
Your append function leaks. It creates two nodes for the first element appended and only saves one of them. Fix:
void append(int x) {
struct Node* a = create_node(x);
if (PythonListHead == NULL) {
PythonListHead = a; // not create_node(x)
} else {
struct Node* cursor = PythonListHead;
while (cursor->next != NULL) {
cursor = cursor->next;
}
cursor->next = a;
}
}
You could simplify append like this:
void append(int x) {
struct Node** cursor = &PythonListHead;
while(*cursor) cursor = &(*cursor)->next;
*cursor = create_node(x);
}
That is, make cursor a pointer to a pointer and initialize it to point at PythonListHead. The while loop will go on until cursor points at a pointer pointing at NULL. Then assign the newly created Node* to the pointer cursor is pointing at. Example: If PythonListHead == NULL, the while loop will not do any loops (*cursor will be equal to NULL) so *cursor = create_node(x); will be the same as PythonListHead = create_node(x);.
Your pop function leaks. If the length is 1 you never delete the node. If len() starts out > 2 it will also continue to run after having called delete_node which makes the program have undefined behavior (and could therefore crash or do just about anything). It also has a logic flaw. If len() returns 1, it will enter the else of if (len()==2) {} else { ... }
if (len()==1) {
}
if (len()==2) { // should have been `else if` here
} else {
// it will enter here if len() == 1 too
}
You also call len() (which is an expensive function) multiple times. Fix:
void pop() {
int length = len(); // only one call to len()
if (length == 1) {
delete_node(PythonListHead); // you forgot to delete here
PythonListHead = NULL;
} else if (length == 2) { // else if
delete_node(PythonListHead->next);
PythonListHead->next = NULL;
} else { // len == 0 or len > 2
struct Node* cursor = PythonListHead;
int count = 0;
while (cursor) {
cursor = cursor->next;
count ;
if (count == (length - 2)) {
delete_node(cursor->next);
cursor->next = NULL;
break; // last is deleted, must break out
}
}
}
}
pop could however be simplified to neither have to use len() nor have special cases for 1 and 2:
void pop() {
for(struct Node** cursor = &PythonListHead; *cursor; cursor = &(*cursor)->next) {
if((*cursor)->next == NULL) {
delete_node(*cursor);
*cursor = NULL;
break;
}
}
}
The pointer to pointer logic is here similar to that in the simplification of append above.