Singly Linked List

Singly Linked List

This code is available on Lab46 under the /var/public/data/fall2012/linkedlist1/ directory in the various source files found therein.

I took the code from class and split it up to be a multi-file C project. I even included a Makefile so you can build the whole thing with make.

linkedlist.h

Set up the structure and list function prototypes.

1

#ifndef __LINKED_LIST_H                                                                   
#define __LINKED_LIST_H
 
#include <stdlib.h>
 
struct node {
    char value;
    struct node *next;
};
typedef struct node Node;
 
char showlist(Node *); 
Node * getpos(Node *, char);
Node * appendnode(Node *, Node *, Node *); 
Node * insertnode(Node *, Node *, Node *); 
Node * removenode(Node *, Node *, Node *); 
 
#endif

append.c

appendnode() is responsible for adding a new node after a specified node. We'll see it used twice- during the initial list building, and later on in a more selective way.

1

#include "linkedlist.h"                                                                   
 
Node * appendnode(Node *begin, Node *pos, Node *newnode)
{
    if ((begin != NULL) && (pos != NULL) && (newnode != NULL))
    {   
        newnode -> next = pos -> next;
        pos -> next = newnode;
    }   
    else if (begin == NULL)
    {   
        begin = pos = newnode;
    }   
 
    return(begin);
}

showlist.c

Display the list, somewhat in set/tuple notation, along with selection markers.

1

#include <stdio.h>                                                                        
#include <stdlib.h>
#include "linkedlist.h"
 
char showlist(Node *mynode)
{
    Node *temp = mynode;
    char i = 0;
 
    printf("{ ");
    while(temp != NULL)
    {   
        printf("([%hhd], %hhd), ", i, temp -> value);
        temp = temp -> next;
        i = i + 1;
    }   
    printf("NULL }\n");
 
    return(i - 1); 
}

getpos.c

Locate node at indicated position and return a pointer to that node.

1

#include "linkedlist.h"                                                                   
 
Node * getpos(Node *begin, char pos)
{
    Node *temp = begin;
    char i;
 
    for(i = 0; i < pos; i++)
        temp = temp -> next;
 
    return(temp);
}

main.c

Sample linked list application. Pulls it all together.

1

#include <stdio.h>                                                                        
#include "linkedlist.h"
 
int main()
{
    Node *start, *tmp, *tmp2;
    char input, i;
 
    start = tmp = tmp2 = NULL;
 
    printf("Phase 1: Building a list\n");
    printf("------------------------\n");
 
    printf("Enter a value (0-127) [-1 to quit]: ");
    scanf("%hhd", &input);
 
    while (input != -1) 
    {   
        tmp2 = (Node *) malloc (sizeof(Node));
        tmp2 -> value = input;
        tmp2 -> next = NULL;
 
        start = appendnode(start, tmp, tmp2);
 
        if (tmp == NULL)
            tmp = start;
 
        if (tmp -> next != NULL)
            tmp = tmp -> next;
 
        printf("Enter a value (0-127) [-1 to quit]: ");
        scanf("%hhd", &input);
    }   
 
    printf("\n\nPhase 2: Displaying the list\n");
    printf("-----------------------------\n");
 
    i = showlist(start);
 
    printf("\n\nPhase 3: Selecting a Node to Append After\n");
    printf("---------------------------------------------\n");
 
    do {
        printf("Select a node # to append after (0-%hhd): ", i); 
        scanf("%hhd", &input);
 
        tmp = getpos(start, input);
    } while (tmp == NULL);
 
    printf("\n\nPhase 4: Append New Node After Specified Node\n");
    printf("-------------------------------------------------\n");
 
    printf("Enter a value (0-127) for new node: ");
    scanf("%hhd", &input);
 
    tmp2 = (Node *) malloc (sizeof(Node));
    tmp2 -> value = input;
    tmp2 -> next = NULL;
 
    start = appendnode(start, tmp, tmp2);
 
    printf("\n\nPhase 5: Displaying the list\n");
    printf("-----------------------------\n");
 
    showlist(start);
 
    return(0);
}

Makefile

To assist with building. Just type make. make clean will clear out all compiled objects. make debug will build with debugging support.

CFLAGS = -Wall                                                                            
INC = 
CC = gcc $(CFLAGS) $(INC) 
SRC = $(shell /bin/ls -1 *.c)
OBJ = $(SRC:.c=.o)
BIN = linkedlistprog
all: $(SRC) $(OBJ) $(BIN)
 
debug: CC += -DDEBUG -g
debug: DEBUG = debug
debug: $(SRC) $(OBJ) $(BIN)
 
linkedlistprog:
ifneq ($(MAKECMDGOALS),debug)
    @printf "[B]   %-20s ... " "$(BIN)"
    @$(CC) -o $(BIN) $(OBJ) && echo "OK" || echo "FAIL"
else
    $(CC) -o $(BIN) $(OBJ)
endif
 
 
.c.o:
ifneq ($(MAKECMDGOALS),debug)
    @printf "[B]   %-20s ... " "$<"
    @$(CC) -c $< && echo "OK" || echo "FAIL"
else
    $(CC) -c $<
endif
 
copy:
    mkdir -p ~/src/data/linkedlist1
    cp -v /var/public/data/fall2012/linkedlist1/* ~/src/data/linkedlist1/
 
clean:
    rm -f $(OBJ) $(BIN) core

Sample Run

Following will be a demonstration of compiling and running this program.

Obtaining a copy

It would be worthwhile to have your own copy of this code to make changes to. Copy it into your ~/src/data/ directory as follows:

lab46:~$ ci /var/public/data/fall2012/linkedlist1
lab46:/var/public/data/fall2012/linkedlist1$ make copy
mkdir -p ~/src/data/linkedlist1
cp -v /var/public/data/fall2012/linkedlist1/* ~/src/data/linkedlist1/
`/var/public/data/fall2012/linkedlist1/Makefile' -> `/home/wedge/src/data/linkedlist1/Makefile'
`/var/public/data/fall2012/linkedlist1/append.c' -> `/home/wedge/src/data/linkedlist1/append.c'
`/var/public/data/fall2012/linkedlist1/getpos.c' -> `/home/wedge/src/data/linkedlist1/getpos.c'
`/var/public/data/fall2012/linkedlist1/insert.c' -> `/home/wedge/src/data/linkedlist1/insert.c'
`/var/public/data/fall2012/linkedlist1/linkedlist.h' -> `/home/wedge/src/data/linkedlist1/linkedlist.h'
`/var/public/data/fall2012/linkedlist1/main.c' -> `/home/wedge/src/data/linkedlist1/main.c'
`/var/public/data/fall2012/linkedlist1/remove.c' -> `/home/wedge/src/data/linkedlist1/remove.c'
`/var/public/data/fall2012/linkedlist1/showlist.c' -> `/home/wedge/src/data/linkedlist1/showlist.c'
lab46:/var/public/data/fall2012/linkedlist1$

Change to your local copy

lab46:/var/public/data/fall2012/linkedlist1$ cd ~/src/data/linkedlist1
lab46:~/src/data/linkedlist1$

Compiling

Let's build it:

lab46:~/src/data/linkedlist1$ make
[B]   append.c             ... OK
[B]   getpos.c             ... OK
[B]   insert.c             ... OK
[B]   main.c               ... OK
[B]   remove.c             ... OK
[B]   showlist.c           ... OK
[B]   linkedlistprog       ... OK
lab46:~/src/data/linkedlist1$

Running

And now, a sample execution:

lab46:~/src/data/linkedlist1$ ./linkedlistprog
Phase 1: Building a list
------------------------
Enter a value (0-127) [-1 to quit]: 2
Enter a value (0-127) [-1 to quit]: 4
Enter a value (0-127) [-1 to quit]: 6
Enter a value (0-127) [-1 to quit]: 8
Enter a value (0-127) [-1 to quit]: 10
Enter a value (0-127) [-1 to quit]: 12
Enter a value (0-127) [-1 to quit]: -1


Phase 2: Displaying the list
-----------------------------
{ ([0], 2), ([1], 4), ([2], 6), ([3], 8), ([4], 10), ([5], 12), NULL }


Phase 3: Selecting a Node to Append After
---------------------------------------------
Select a node # to append after (0-5): 2


Phase 4: Append New Node After Specified Node
-------------------------------------------------
Enter a value (0-127) for new node: 7


Phase 5: Displaying the list
-----------------------------
{ ([0], 2), ([1], 4), ([2], 6), ([3], 7), ([4], 8), ([5], 10), ([6], 12), NULL }
lab46:~/src/data/linkedlist1$

Table of Contents

Singly Linked List

linkedlist.h

append.c

showlist.c

getpos.c

main.c

Makefile

Sample Run

Obtaining a copy

Change to your local copy

Compiling

Running