My project this week is to perform basic linked list operations. We didn't learn this in class, and the TA that attempted to explain can't speak English very well, so I'm having trouble understanding what I'm doing wrong. I linked the entire file, but I only had to implement the functions LinkedListLength, InsertAtEnd, InsertAtN, and DeleteNode. I'm pretty sure I have the LinkedListLength function correct, but the last three don't seem to work. Any help would be greatly appreciated!

/*
 * node.c
 */
#include <stdio.h>
#include <stdlib.h>
#include "node.h"

/* This function allocates space for a new node and
 * returns the pointer to this new node.
 * This function should be called while creating a new node
 * */
struct node* CreateNode() {
        return malloc(sizeof(struct node));
}

/* Print the linked list with head pointing to the first node
 * For an empty linked list, print NULL
 * */
void PrintList(struct node* head) {
        struct node* current = head;

        while(current != NULL) {
                printf("%d ", current->data);
                current = current->next;
        }
        printf("NULL\n");
}


/* Function: Insert a new node in front of linked list
 * Input:
 *    head: pointer to the start of linked list
 *    value: data field for new node
 * Return: new linked list after inserting the node
 * */
struct node* InsertInFront(struct node* head, int value) {
        struct node* newNode = CreateNode();
        newNode->data = value;
        newNode->next = head;
        return newNode;
}

/* Function: to create a new linked list
 * Input:
 *    values[]: array of integers containing values for data fields
 *    len: length of values[] array
 * Return: New linked list where each node data contains
 *         a value from values[] array
 * */
struct node* CreateList(int values[], int len) {
        // check for empty list
        if (len == 0) return NULL;
        struct node* head = NULL;
        int i;
        for(i=len; i>0; i--) {
                head = InsertInFront(head, values[i-1]);

        }
        return head;
}

/* ---------------------------------------------------------
 * ------- IMPLEMENT THE FUNCTIONS BELOW -------------------
 * ---------------------------------------------------------*/


/* Function: Compute the length of linked list
 * Input:
 *    head: pointer to the start of linked list
 * Return: length of the linked list
 */
int LinkedListLength(struct node* head) {

        struct node *temp = head;
        int i = 0;

        while(temp != NULL){
                temp = temp -> next;
                i++;
        }

        return i;
}


/* Function: Insert a new node at the end of linked list
 * Input:
 *    head: pointer to the start of linked list
 *    value: data field for new node
 * Return: new linked list after inserting the node
 * */
struct node* InsertAtEnd(struct node* head, int value) {

        struct node *temp = head;
        int i = 1;
        struct node *newNode;

        while (temp != NULL){
                if(temp -> next == NULL){
                        newNode = CreateNode();
                        newNode -> data = value;
                        newNode -> next = NULL;

                        return head;
                }

                temp = temp -> next;
                i++;
        }

        return head;
}

/* Function: Insert a new node with given data
 * Input:
 *    head: pointer to the start of linked list
 *    value: value to be stored in data field of new node
 *    N: position of node AFTER which new node should be inserted
 *       If N=0, then new node should be inserted in front (Special case)
 * Error: If invalid N, output error:
 *    ERROR: Node <N> does not exist
 */
struct node* InsertAtN(struct node* head, int value, int N) {

        int i = 1;

        struct node *temp = head;

        if(N > LinkedListLength(head)){
                printf("ERROR: Node <N> does not exist");
        }

        if(N == 0){
                InsertInFront(head, value);
        }

        struct node *newNode;

        while (i <= N){
                if(i == N){
                        newNode = CreateNode();
                        newNode -> data = value;
                        newNode -> next = temp -> next;
                        temp = newNode;

                        return head;
                }

                temp = temp -> next;
                i++;
        }

        return head;
}

/* Function: Deletes a node at a given position from linked list
 * Input:
 *    head: pointer to the start of linked list
 *    pos: position of node to delete from linked list (pos is in [1,length])
 * Return: new linked list after deleting the node
 * Error: If node to be deleted does not exist, output:
 *    ERROR: Node does not exist
 */
struct node* DeleteNode(struct node* head, int pos) {

        struct node *temp = head;

        if(pos > LinkedListLength(head)){
                printf("ERROR: Node does not exist");
        }

        int i = 1;

        struct node *newNode;

        while(i < pos){
                if(i+1 == pos){
                        temp = temp -> next -> next;
                        free(temp -> next);

                        return head;
                }

                temp = temp -> next;
                i++;
        }



        return newNode;
}

The parameters to some functions are incorrect -- you have to pass a pointer to a pointer if you want a function to change the calling function's pointer. Example:

struct node* InsertAtEnd(struct node** head, int value) {  
   struct node* newnode = CreteNode();
   newnode->data = value;
   newnode->next = NULL;
   if( *head == NULL)
       *head = newnode;
   else
   {
        // locate list tail and insert newnode there
   }
   return newnode;  
}

int main()
{
    struct node* head = NULL;
     InsertAtEnd(&head,1);
}

Edited 5 Years Ago by Ancient Dragon: n/a

The parameters to some functions are incorrect -- you have to pass a pointer to a pointer if you want a function to change the calling function's pointer. Example:

struct node* InsertAtEnd(struct node** head, int value) {  
   struct node* newnode = CreteNode();
   newnode->data = value;
   newnode->next = NULL;
   if( *head == NULL)
       *head = newnode;
   else
   {
        // locate list tail and insert newnode there
   }
   return newnode;  
}

int main()
{
    struct node* head = NULL;
     InsertAtEnd(&head,1);
}

The prototypes of the functions were written by the TAs/professor, so I don't think that's the problem. I guess what I need help with is the logic to performing these operations. Sorry if I'm misunderstanding you, I'm new to C and programming in general.

Hey Manske I am actually in your class haha.

Anyways, I got mine working after getting some help.

What I figured out what I was doing wrong was I wasn't passing the correct pointer (head) back in the return statement. (I'm refering to your DeleteNode() method)

Hopefully that is a push in the correct direction.

This article has been dead for over six months. Start a new discussion instead.