#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    101
    Rep Power
    0

    An efficient way to create linked lists?


    I'm still on the look out to understanding linked lists (doubly linked lists and Binary Tree.). Can you tell me, is this an efficient way to create a linked list?

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct school {
    	char *subject;
    	short grade;
    	struct school *period;
    } school;
    
    void ReportCard(school *student)
    {
    	if(!student)
    	{
    		return;
    	}
    	else
    	{
    		printf("%s: \t %d\n",student->subject,student->grade);
    		ReportCard(student->period);
    	}
    }
    
    void Quarter(school *student)
    {
    	if(student == NULL)
    	{
    		return;
    	}
    	Quarter(student->period);
    	free(student);
    }
    
    int main()
    {
    	school *SS = (school *)malloc(sizeof(school));
    	school *math = (school *)malloc(sizeof(school));
    	school *reading = (school *)malloc(sizeof(school));
    	school *science = (school *)malloc(sizeof(school));
    	SS->grade = 93;
    	SS->subject = "Social Studies";
    	math->grade = 95;
    	math->subject = "Algebra";
    	reading->grade = 88;
    	reading->subject = "R/LA";
    	science->grade = 91;
    	science->subject = "Chemistry";
    	SS->period = math;
    	math->period = reading;
    	reading->period = science;
    	science->period = NULL;
    	ReportCard(SS);
    	getchar();
    	Quarter(SS);
    	return 0;
    }
    A few tutorials I've seen done the code this way and it seems fine to me to understand. But I'm asking, is it really efficient?

    And like I said before, do any of you know a good tutorial on double linked lists or binary search trees? I did try that confuzzled site but it seemed too long and my computer started lagging a bit after going through it a while. Plus, I fully didn't understand it.

    Any recommendations would be great. Thanks to you all!
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,377
    Rep Power
    1871
    The big problem is you're creating separately named nodes for each element of your list. Whilst this is fine (upto 4) for constant data, if you were reading from a file, you would be well and truly stuck.

    Plus, you're not helping yourself with poorly chosen names for things.
    - A school isn't a list of subjects and grades.
    - Quarter is an awful name for something which deletes a linked list.

    Code:
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    typedef struct score {
      char    *subject;
      short    grade;
      struct score *next;
    } score;
    
    // Node Functions
    // ==============
    score *createNode ( const char *subject, short grade ) {
      score *result = malloc( sizeof(*result) );
      result->subject = malloc( strlen(subject) + 1 );
      strcpy(result->subject,subject);
      result->grade = grade;
      result->next = NULL;
      return result;
    }
    void printNode ( score *node ) {
      printf("%s %hd\n", node->subject, node->grade );
    }
    void freeNode ( score *node ) {
      free( node->subject );
      free( node );
    }
    
    // List Functions
    // ==============
    score *appendToList ( score *list, const char *subject, short grade ) {
      score *newNode = createNode(subject,grade);
      if ( list == NULL ) {
        list = newNode;
      } else {
        score *temp = list;
        while ( temp->next != NULL ) temp = temp->next;
        temp->next = newNode;
      }
      return list;
    }
    
    void printList ( score *list ) {
      score *current = list;
      while ( current != NULL ) {
        printNode(current);
        current = current->next;
      }
    }
    
    void freeList ( score *list ) {
      while ( list != NULL ) {
        score *temp = list;
        list = list->next;
        freeNode( temp );
      }
    }
    
    int main ( ) {
      score *list = NULL;
      list = appendToList(list,"Social Studies",93);
      list = appendToList(list,"Algebra",95);
      list = appendToList(list,"R/LA",88);
      list = appendToList(list,"Chemistry",91);
      printList(list);
      freeList(list);
      return 0;
    }
    Things to take note of.
    1. The separation of 'node' and 'list' functions. The node functions just deal with the data, where the list functions just deal with list navigation.
    2. Each function does one very simple thing. A typical failing is to try and do too much in a single function.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper

IMN logo majestic logo threadwatch logo seochat tools logo