PROJECT: SINGLY LINKED LISTS (sll0)

OBJECTIVE

Undertaking our first data structure implementation for the semester.

TASK

By the deadline, please do the following:

• implement your own singly-linked list implementation, in C:
  • Node struct, containing a value integer and a next Node pointer
  • Node *mknode (int);
  • Node *insert (Node *, Node *, Node *);
  • Node *append (Node *, Node *, Node *);
  • Node *obtain (Node **, Node *);
  • Node *rmnode (Node *);
• test your linked-list implementation

NODE STRUCT

The core of the linked list is the Node, the unit that is transacted within the data structure.

For our current minimal purposes, your node should contain at least two items:

• value, an integer
• next, a pointer to a Node

MKNODE()

To facilitate the creation of nodes, write an mknode() function that manages the memory allocation, checking of successful allocation, and assignment of payload (value), and initializing next to NULL.

Memory is allocated with malloc(3). Be sure to properly case its return value to your node pointer type.

On error, mknode() should return NULL.

INSERT()

There are two ways to add nodes into a list. The insert() function will add a node before an indicated node in the list.

The parameters are as follows:

• pointer to the start of the list
• pointer to the node in the list you'd like to insert before
• pointer to the node you'd like to insert into the list

A pointer to the start of the list is returned.

You should check to make sure the involved things are not NULL (as a segmentation fault would occur otherwise).

Make use of the minimal number of needed temporary pointers. Remember not to micro-manage.

You will need to manage cases of null and empty lists.

Make sure to keep the start of list pointer updated.

APPEND()

There are two ways to add nodes into a list. The append() function will add a node after an indicated node in the list.

The parameters are as follows:

• pointer to the start of the list
• pointer to the node in the list you'd like to append after
• pointer to the node you'd like to insert into the list

A pointer to the start of the list is returned.

You should check to make sure the involved things are not NULL (as a segmentation fault would occur otherwise).

Make use of the minimal number of needed temporary pointers. Remember not to micro-manage.

You will need to manage cases of null and empty lists.

Make sure to keep the start of list pointer updated.

OBTAIN()

To get a node out of the list, we obtain() it. This function will isolate a node in a list, maintaining continuity of the remaining list.

The parameters are as follows:

• double pointer to the start of the list
• single pointer to the node you'd like to obtain

A pointer to the now-isolated node is returned.

You should make sure to check for any NULL values before dereferencing pointers (to avoid segmentation faults).

Make use of the minimal number of needed temporary pointers. Remember not to micro-manage.

You will need to manage cases of null and empty lists.

Make sure to keep the start of list pointer updated.

RMNODE()

To deallocate a standalone node, you pass it to rmnode(). This function will mark the allocated memory for deallocation (with free(3)), and set the pointer to NULL, returning that pointer.

Be sure to check things for NULL (you don't want to free() a NULL)

SUBMISSION

52:sll0:final tally of results (26/26)
*:sll0:implement node struct and mknode, rmnode functions [13/13]
*:sll0:implement and test insert function [13/13]
*:sll0:implement and test append function [13/13]
*:sll0:implement and test obtain function [13/13]

Additionally:

• Solutions not abiding by spirit of project will be subject to a 25% overall deduction
• Solutions not utilizing descriptive why and how comments will be subject to a 25% overall deduction
• Solutions not utilizing indentation to promote scope and clarity will be subject to a 25% overall deduction
• Solutions not organized and easy to read (assume a terminal at least 90 characters wide, 40 characters tall) are subject to a 25% overall deduction