Online Test Banks
Score higher
See Online Test Banks
eLearning
Learning anything is easy
Browse Online Courses
Mobile Apps
Learning on the go
Explore Mobile Apps
Dummies Store
Shop for books and more
Start Shopping

How to Create a Linked List in C Programming

In C programming, if you want to add a second structure to code you’ve already created, create a linked list — a series of structures that contain pointers to each other. Along with the basic data in a structure, the structure contains a pointer, which contains the address of the next structure in the list.

With some clever juggling of pointer names, plus a NULL to cap the end of the list, you might end up with something similar to the source code in A Primitive Linked-List Example.

A PRIMITIVE LINKED-LIST EXAMPLE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
 struct stock {
 char symbol[5];
 int quantity;
 float price;
 struct stock *next;
 };
 struct stock *first;
 struct stock *current;
 struct stock *new;
/* Create structure in memory */
 first=(struct stock *)malloc(sizeof(struct stock));
 if(first==NULL)
 {
 puts("Some kind of malloc() error");
 exit(1);
 }
/* Assign structure data */
 current=first;
 strcpy(current->symbol,"GOOG");
 current->quantity=100;
 current->price=801.19;
 current->next=NULL;
 new=(struct stock *)malloc(sizeof(struct stock));
 if(new==NULL)
 {
 puts("Another malloc() error");
 exit(1);
 }
 current->next=new;
 current=new;
 strcpy(current->symbol,"MSFT");
 current->quantity=100;
 current->price=28.77;
 current->next=NULL;
/* Display database */
 puts("Investment Portfolio");
 printf("Symbol\tShares\tPrice\tValue\n");
 current=first;
 printf("%-6s\t%5d\t%.2f\t%.2f\n",\
 current->symbol,
 current->quantity,
 current->price,
 current->quantity*current->price);
 current=current->next;
 printf("%-6s\t%5d\t%.2f\t%.2f\n",\
 current->symbol,
 current->quantity,
 current->price,
 current->quantity*current->price);
 return(0);
}

This source code is pretty long, but it simply creates a second structure, linked to the first one. Don’t let the source code’s length intimidate you.

Lines 13 through 15 declare the standard three structure pointers that are required for a linked-list dance. Traditionally, they’re named first, current, and new. They play into the fourth member in the structure, next, found at Line 11, which is a structure pointer.

Don’t use typedef to define a new structure variable when creating a linked list. A Primitive Linked-List Example doesn’t use typedef, so it’s not an issue with the code, but many C programmers use typedef with structures. Be careful!

The variable name new, used in Line 15, is a reserved word in C++, so if you want to be bilingual, change the variable name to new_struct or to something other than the word new.

When the first structure is filled, Line 30 assigns a NULL pointer to the next element. That NULL value caps the end of the linked list.

Line 32 creates a structure, placing its address in the new pointer variable. The address is saved in the first structure in Line 38. That’s how the location of the second structure is retained.

Lines 40 through 43 fill information for the second pointer, assigning a NULL value to the next element at Line 43.

The linking takes place as the structures’ contents are displayed. Line 48 captures the first structure’s address. Then Line 54 captures the next structure’s address from within the first structure.

Exercise 1: Type the source code from A Primitive Linked-List Example into your editor. Even though it’s long, type it in because you’ll need to edit it again later (if you’re not used to that by now). Build and run.

image0.jpg

Unlike arrays, structures in a linked list are not numbered. Instead, each structure is linked to the next structure in the list. As long as you know the address of the first structure, you can work through the list until the end, which is marked by a NULL.

A Primitive Linked-List Example shows some sloppy source code with lots of repeated code. When you see multiple statements like this in your code, you should immediately think “functions.”

A BETTER LINKED-LIST EXAMPLE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ITEMS 5
struct stock {
 char symbol[5];
 int quantity;
 float price;
 struct stock *next;
};
struct stock *first;
struct stock *current;
struct stock *new;
struct stock *make_structure(void);
void fill_structure(struct stock *a,int c);
void show_structure(struct stock *a);
int main()
{
 int x;
 for(x=0;x<ITEMS;x++)
 {
 if(x==0)
 {
 first=make_structure();
 current=first;
 }
 else
 {
 new=make_structure();
 current->next=new;
 current=new;
 }
 fill_structure(current,x+1);
 }
 current->next=NULL;
/* Display database */
 puts("Investment Portfolio");
 printf("Symbol\tShares\tPrice\tValue\n");
 current = first;
 while(current)
 {
 show_structure(current);
 current=current->next;
 }
 return(0);
}
struct stock *make_structure(void)
{
 struct stock *a;
 a=(struct stock *)malloc(sizeof(struct stock));
 if(a==NULL)
 {
 puts("Some kind of malloc() error");
 exit(1);
 }
 return(a);
}
void fill_structure(struct stock *a,int c)
{
 printf("Item #%d/%d:\n",c,ITEMS);
 printf("Stock Symbol: ");
 scanf("%s",a->symbol);
 printf("Number of shares: ");
 scanf("%d",&a->quantity);
 printf("Share price: ");
 scanf("%f",&a->price);
}
void show_structure(struct stock *a)
{
 printf("%-6s\t%5d\t%.2f\t%.2f\n",\
 a->symbol,
 a->quantity,
 a->price,
 a->quantity*a->price);
}

Most linked lists are created as shown in A Better Linked-List Example. The key is to use three structure variables, shown in Lines 13 through 15:

  • first always contains the address of the first structure in the list. Always.

  • current contains the address of the structure being worked on, filled with data, or displayed.

  • new is the address of a new structure created by using the malloc() function.

Line 7 declares the stock structure as global. That way, it can be accessed from the various functions.

The for loop between Lines 25 and 39 creates new structures, linking them together. The initial structure is special, so its address is saved in Line 30. Otherwise, a new structure is allocated, thanks to the make_structure() function.

In Line 35, the previous structure is updated; the value of current isn’t changed until Line 36. Before that happens, the pointer in the current structure is updated with the address of the next structure, new.

At Line 40, the end of the linked list is marked by resetting the new pointer in the last structure to a NULL.

The while loop at Line 46 displays all structures in the linked list. The loop’s condition is the value of the current pointer. When the NULL is encountered, the loop stops.

The rest of the code shown in A Better Linked-List Example consists of functions that are pretty self-explanatory.

Exercise 2: Copy the code from A Better Linked-List Example into the editor. Build and run.

Take note of the scanf() statements in the fill_structure() function. Remember that the -> is the “peeker” notation for a pointer. To get the address, you must prefix the variable with an & in the scanf() function.

  • Add a Comment
  • Print
  • Share
blog comments powered by Disqus
Advertisement

Inside Dummies.com

Dummies.com Sweepstakes

Win $500. Easy.