======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.

<code c 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
</code>

=====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.

<code c 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);
}
</code>

=====showlist.c=====

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

<code c 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); 
}
</code>

=====getpos.c=====

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

<code c 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);
}
</code>

=====main.c=====

Sample linked list application. Pulls it all together.

<code c 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);
}
</code>
=====Makefile=====

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

<code 1>
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
</code>

=====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:

<cli>
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$ 
</cli>

====Change to your local copy====

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

====Compiling====

Let's build it:

<cli>
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$ 
</cli>

====Running====

And now, a sample execution:

<cli>
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$ 
</cli>