CS240 Spring 2011: LAB04
Goal
Implement linkedlist, a program which provides the following functionality for creating, manipulating and printing a linked list.
Do not use
Arrays for implementing linked list. Linked list implementation MUST be done
using structures and pointers.
Introduction
Linked list is a data structure which stores data in elements called nodes. Each node consists of data field and a link (a pointer) to the next node. The last node points to NULL.
For example, suppose you want to store number 75, 53, 29 in a linked list. The linked list looks something like this:
A
node in linked list can be implemented using struct.
For example: struct node { A
linked list is a list of pointers to struct
node. Whenever you create a pointer to a new node, you will need to
dynamically allocate memory for that node. To do this, we have provided you
with a function CreateNode() which will allocate memory for storing the new node and
return a pointer to it. An
example of using CreateNode(). Suppose you want to create a new node and store integer
5 in it. Here is how you will do it: struct node* newNode = CreateNode(); Note
that if you try to store data in a newNode without allocating
memory, it will result in a segmentation fault. We
have also provided you with implementation for printing a linked list,
inserting a node in front and creating a linked list. Use this code to
understand how to operate on linked lists. 1.
Download lab04.tar
from here and extract it using: tar -xpvf lab04.tar 2.
This folder contains 3 source files: node.h, node.c and main.c 3.
You have to implement the functions for linked
list manipulation in node.c.
The function prototypes are already present in this file. You should follow
these prototypes (Do not modify the function prototype by changing the type of
arguments or return type). 4.
You need to implement the following
functionality: Function Description int LinkedListLength(struct node* head) Function: Compute the length of
linked list struct node* InsertAtEnd(struct node* head, int value) Function: Insert a new node at
the end of linked list struct node* InsertAtN(struct node* head, int value, int N) Function: Insert a new node with
given data struct node* DeleteNode(struct node* head, int pos) Function: Deletes a node at a
given position from linked list 5.
Also write a Makefile to compile your code.
The main target should be named as linkedlist 6.
The main.c file has test cases to test your code. To
test the code, you can run: 7.
A reference implementation, linkedlist.org, is also present in the
lab04.tar. Make sure your output
is exactly the same as reference implementation. 8. Make
sure you check for error conditions and the boundary cases in your code. Type
cd .. in lab04 and
change working directory to the parent directory of lab04. In
the parent directory of lab04,
type turnin -v -c cs240=XXX -p lab04 lab04
to turnin your work. Replace XXX with your section
number-- F1130, F130, F330, F730, F930, R1130, R330, R930, T1130.
Now,
you may use the command, turnin -c cs240=XXX -p lab04 -v to verify your
submission. This
lab is due on Wednesday 16 February 11:59PM. 9:30
am - 11:20 am F F930 11:30
am - 1:20 pm F F1130 1:30
pm - 3:20 pm F F130 3:30
pm - 5:20 pm F F330 9:30
am - 11:20 am R R930 11:30
am - 1:20 pm R R1130 3:30
pm - 5:20 pm R R330 11:30
am - 1:20 pm T T1130
int
data; //data contained in the node. This can be of any type – char,
char*, int, or even a struct
struct
node *next; //pointer to next node
};
newNode->data = 5;
newNode->next = NULL;Instructions
Input:
head: pointer to the
start of linked list Return: length of the 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
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
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
$ linkedlist
<testcase-number>Submit