Correct List.c and List.h to make this program a true circular doubly linked lis
ID: 3675066 • Letter: C
Question
Correct List.c and List.h to make this program a true circular doubly linked list. IE. For the insert, get, and remove functions, you should be able to put in an index that is greater than the size of the linked list or a big negative indices and it will just loop around and insert it into the correct location WITHOUT USING A FORM OF MODULOUS OR LOOPS.
#ifndef NODE_H
#define NODE_H
typedef struct node* Node;
Node createNode(int value);
int getValue(Node);
Node getNext(Node);
Node getPrevious(Node);
void setValue(Node, int value);
void setNode(Node, Node previous);
void setNext(Node, Node next);
void freeNode(Node);
#endif
-----------------------------------------------------------------------------------
#include
#include "node.h"
struct node
{
int value;
Node next;
Node previous;
};
Node createNode(int value)
{
Node newNode = malloc(sizeof *newNode);
newNode -> value = value;
newNode -> next = NULL;
newNode -> previous = NULL;
return newNode;
}
//get the value of a node
int getValue(Node current)
{
return current -> value;
}
//get the next node
Node getNext(Node current)
{
return current -> next;
}
//get the previous node
Node getPrevious(Node current)
{
return current -> previous;
}
//set the value of a node
void setValue(Node current, int value)
{
current -> value = value;
}
//set the node itself
void setNode(Node current, Node previous)
{
current -> previous = previous;
}
//set the next node
void setNext(Node current, Node next)
{
current -> next = next;
}
//free the node
void freeNode(Node current)
{
free(current);
}
----------------------------------------------------------------------------------------------
#ifndef LIST_H
#define LIST_H
//create a handle for lists
typedef struct list* List;
/* Creates a new non-circular singly-linked list
* @return returns a new empty list
*/
List createList();
/* Get the size of the linked list
* @param List the list we need the size of
* @return the size of the linked list
*/
int size(List);
/* Adds an element to the beginning of a linked list
* @param List the list to add elements to
* @param value the item to add to the beginning of the list
*/
void prepend(List,int value);
/* Adds an element to the end of a linked list
* @param List the list to add elements to
* @param value the item to add to the end of the list
*/
void append(List,int value);
/* Inserts an element into a position in the linked list
* @param List the list to insert elements into
* @param index where to insert the element
* @param value the item to insert into the list
*/
void insert(List, int index, int value);
/* Removes an element from a position in the linked list
* @param List the list to remove elements from
* @param index where to remove the element from
* @return the value of the element that was removed
*/
int removeAt(List, int index);
/* Gets an element from a position in the linked list without removing
* @param List the list to get the element from
* @param index where to get the element from
* @return the value of the element that was retrieved
*/
int get(List, int index);
/* Prints the elements in the list
* @param List the list to print out
*/
void printList(List);
/*Prints the element from the end of the list
*
*/
void printListFromEnd();
/*Displays the menu
*
*/
void menu();
/* Frees the memory allocated for the list
* @param List the list to free
*/
void freeList(List);
#endif
----------------------------------------------------------------------------------------------
#include
#include
#include "list.h"
#include "node.h"
struct list
{
int size;
Node head;
Node previous;
};
//creation of a new list
List createList()
{
List newList = malloc(sizeof *newList);
newList -> size = 0;
newList -> head = NULL;
newList -> previous = NULL;
return newList;
}
//return size of the list
int size(List currentList)
{
return currentList -> size;
}
//add an element to the beginning of the circular linked list
void prepend(List currentList, int value)
{
//create the new node that we are adding which points to old head
Node newNode = createNode(value);
++currentList -> size;
//if head is currently points to something, it will move it to the new node that was created in the list
if(currentList -> head == NULL)
{
currentList -> head = newNode;
currentList -> previous = newNode;
return;
}
else
{
setNode(currentList -> head, newNode);
setNext(newNode, currentList -> head);
currentList -> head = newNode;
}
if(currentList -> previous == NULL)
currentList -> previous = currentList -> head;
}
//add an item to the end of the linked list
void append(List currentList, int value)
{
//create the new node that we are going to add
Node newNode = createNode(value);
++currentList -> size;
//head and previous should point here if no new nodes have been added
if(currentList -> previous == NULL)
{
currentList -> head = newNode;
currentList -> previous = currentList -> head;
return;
}
//otherwise, the old previous will need to point to this new node
setNext(currentList -> previous, newNode);
setNode(newNode, currentList -> previous);
//update the previous pointer so the new node is our new previous
currentList -> previous = newNode;
}
void insert(List currentList, int index, int value)
{
if(index == 0)
{
prepend(currentList, value);
return;
}
if(index == currentList -> size)
{
append(currentList, value);
return;
}
//cheater insert @ for pos numbers for testing
// if(index > currentList->size)
// {
// while(index > currentList->size)
// index = index - (currentList->size);
// append(currentList, value);
// return;
// }
//loop to where we will insert the value
Node currentNode = currentList->head;
//loop until we are before where we want to insert
int i;
for(i = 0; i < index - 1; ++i)
currentNode = getNext(currentNode);
//create a new node and point it to the current node's next
Node newNode = createNode(value);
if(currentNode == NULL)
{
setNext(getNext(currentNode), newNode);
setNext(newNode, NULL);
setNode(newNode, currentNode);
}
else
{
setNext(newNode, getNext(currentNode));
setNode(getNext(newNode), newNode);
setNext(currentNode, newNode);
setNode(newNode, currentNode);
}
++currentList -> size; //increase size of the list
}
//remove an element at a declared index
int removeAt(List currentList, int index)
{
//test to ensure the index is within the available indexes currently used
if(currentList -> size == 0)
{
printf("Cannot remove the element from the list. ");
exit(1);
}
//start at the beginning of the linked list
Node currentNode = currentList->head;
--currentList->size;
//loop until we are before where we want to remove
int i;
for(i = 0; i < index; ++i)
currentNode = getNext(currentNode);
if(getPrevious(currentNode) != NULL)
setNext(getPrevious(currentNode), getNext(currentNode));
if(getNext(currentNode) != NULL)
setNode(getNext(currentNode), getPrevious(currentNode));
if(currentList->head == currentNode)
currentList -> head = getNext(currentNode);
if(currentList -> previous == currentNode)
currentList -> previous = getPrevious(currentNode);
int value = getValue(currentNode);
free(currentNode);
return value;
}
//get an item at a specified index, NOT removed!!!
int get(List currentList, int index)
{
//ensure list is not empty and the element is within the index range
if(currentList -> size == 0)
{
printf("Cannot remove the element from the list. ");
exit(1);
}
//start at the beginning of the linked list
Node currentNode = currentList->head;
--currentList->size;
//loop until we are before where we want to print
int i;
for(i = 0; i < index; ++i)
currentNode = getNext(currentNode);
int value = getValue(currentNode);
return value;
}
//used to print out the list in the current order
void printList(List currentList)
{
Node currentNode = currentList -> head;
while(currentNode != NULL)
{
printf("%d",getValue(currentNode));
if(getNext(currentNode) != NULL)
printf(" ");
currentNode = getNext(currentNode);
}
printf(" ");
}
//used to print out the list in the reverse order
void printListFromEnd(List currentList)
{
Node currentNode = currentList -> previous;
while(currentNode != NULL)
{
printf("%d",getValue(currentNode));
if(getPrevious(currentNode) != NULL)
printf(" ");
currentNode = getPrevious(currentNode);
}
printf(" ");
}
//the freeing of everything
void freeList(List currentList)
{
Node currentNode = currentList -> head; //start at head
while(currentNode != NULL)
{
Node next = getNext(currentNode);
free(currentNode);
currentNode = next;
}
free(currentList);
}
//the menu
void menu()
{
printf(" What would you like to do to your linked list?");
printf(" 1. Get the current size of the linked list.");
printf(" 2. Prepend an item to the linked list.");
printf(" 3. Append an item to the linked list.");
printf(" 4. Insert an item into the linked list.");
printf(" 5. Remove an item from the linked list.");
printf(" 6. Get an item at a specific position in the linked list.");
printf(" 7. Print the list in the forward direction.");
printf(" 8. Print the list in the reverse direction. ");
printf(" 9. Exit the program. ");
}
--------------------------------------------------------------------------------------------------
#include
#include
#include "node.h"
#include "list.h"
int main()
{
List currentList = createList();
int selection; //menu selection
int response; //yes/no selection
int index; //node index of list
int item;
do
{
menu();
printf(" Please enter your selection: ");
scanf("%d", &selection);
while(selection < 1 || selection > 9)
{
printf(" I am sorry, but that is not a valid choice");
printf(" Input a choice between 1 and 9: ");
scanf("%d", &selection);
}
switch(selection)
{
case 1:
printf("The current size of the list is: %d", size(currentList));
break;
case 2:
printf("Enter the item you would like to insert at the front of the list: ");
scanf("%d", &item);
prepend(currentList, item);
break;
case 3:
printf("Enter the item you would like to insert at the end of the list: ");
scanf("%d", &item);
append(currentList, item);
break;
case 4:
printf("Enter the item you would like to insert into the list: ");
scanf("%d", &item);
printf("Enter the index you would like the item stored at: ");
scanf("%d", &index);
insert(currentList, index, item);
break;
case 5:
printf("Enter the index you want the item removed from: ");
scanf("%d", &index);
printf("Item removed: %d",removeAt(currentList,index));
break;
case 6:
printf("Enter the index of the item you want to print out: ");
scanf("%d", &index);
printf("The element at that index is: %d", get(currentList, index));
break;
case 7:
printList(currentList);
break;
case 8:
printListFromEnd(currentList);
break;
case 9:
exit(1);
break;
default:
printf(" Invalid Choice");
}
printf(" Would you like to continue? ");
printf("Press 1 for YES and 2 for NO: ");
scanf("%d", &response);
while(response < 1 || response > 2)
{
printf("Please enter 1 for YES or 2 for NO: ");
scanf("%d", &response);
}
}while(response == 1);
return 0;
}
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include "node.h"
struct node* CreateNode() {
return malloc(sizeof(struct node));
}
void PrintList(struct node* head) {
struct node* current = head;
while(current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("NULL ");
}
struct node* InsertInFront(struct node* head, int value) {
struct node* newNode = CreateNode();
newNode->data = value;
newNode->next = head;
return newNode;
}
struct node* CreateList(int values[], int len) {
// check for empty list
if (len == 0) return NULL;
struct node* head = NULL;
int i;
for(i=len; i>0; i--) {
head = InsertInFront(head, values[i-1]);
}
return head;
}
int LinkedListLength(struct node* head) {
struct node *temp = head;
int i = 0;
while(temp != NULL){
temp = temp -> next;
i++;
}
return i;
}
struct node* InsertAtEnd(struct node* head, int value) {
struct node *temp = head;
int i = 1;
struct node *newNode;
while (temp != NULL){
if(temp -> next == NULL){
newNode = CreateNode();
newNode -> data = value;
newNode -> next = NULL;
return head;
}
temp = temp -> next;
i++;
}
return head;
}
struct node* InsertAtN(struct node* head, int value, int N) {
int i = 1;
struct node *temp = head;
if(N > LinkedListLength(head)){
printf("ERROR: Node <N> does not exist");
}
if(N == 0){
InsertInFront(head, value);
}
struct node *newNode;
while (i <= N){
if(i == N){
newNode = CreateNode();
newNode -> data = value;
newNode -> next = temp -> next;
temp = newNode;
return head;
}
temp = temp -> next;
i++;
}
return head;
}
struct node* DeleteNode(struct node* head, int pos) {
struct node *temp = head;
if(pos > LinkedListLength(head)){
printf("ERROR: Node does not exist");
}
int i = 1;
struct node *newNode;
while(i < pos){
if(i+1 == pos){
temp = temp -> next -> next;
free(temp -> next);
return head;
}
temp = temp -> next;
i++;
}
return newNode;
}-----------------------------------------------------------------------------------------------------------------------------------------------------
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
void removeDuplicates(struct node *start)
{
struct node *ptr1, *ptr2, *dup;
ptr1 = start;
while(ptr1 != NULL && ptr1->next != NULL)
{
ptr2 = ptr1;
while(ptr2->next != NULL)
{
if(ptr1->data == ptr2->next->data)
{
/* sequence of steps is important here */
dup = ptr2->next;
ptr2->next = ptr2->next->next;
free(dup);
}
else /* This is tricky */
{
ptr2 = ptr2->next;
}
}
ptr1 = ptr1->next;
}
}
void push(struct node** head_ref, int new_data);
void printList(struct node *node);
int main()
{
struct node *start = NULL;
push(&start, 10);
push(&start, 11);
push(&start, 12);
push(&start, 11);
push(&start, 11);
push(&start, 12);
push(&start, 10);
printf(" Linked list before removing duplicates ");
printList(start);
removeDuplicates(start);
printf(" Linked list after removing duplicates ");
printList(start);
getchar();
}
void push(struct node** head_ref, int new_data)
{
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
-----------------------------------------------------------------------------------------------------------------------------------------------------public class Node {
int cargo;
Node next;
public Node () {
cargo = 0;
next = null;
}
public Node (int cargo, Node next) {
this.cargo = cargo;
this.next = next;
}
public String toString () {
return cargo + "";
}
}
The declarations of the instance variables follow naturally from the specification, and the rest follows mechanically from the instance variables. The expression cargo + "" is an awkward but concise way to convert an integer to a String.
To test the implementation so far, we would put something like this in main:
Node node = new Node (1, null);
System.out.println (node);
The result is simply
1
To make it interesting, we need a list with more than one node!
Node node1 = new Node (1, null);
Node node2 = new Node (2, null);
Node node3 = new Node (3, null);
------------------------------------------------------------------
void add(int x)
{
if (hash.get(x) != null)
return;
int s = arr.size();
arr.add(x);
hash.put(x, s);
}
void remove(int x)
{
Integer index = hash.get(x);
if (index == null)
return;
hash.remove(x);
int size = arr.size();
Integer last = arr.get(size-1);
Collections.swap(arr, index, size-1);
arr.remove(size-1);
hash.put(last, index);
}
int getRandom()
{
Random rand = new Random(); // Choose a different seed
int index = rand.nextInt(arr.size());
return arr.get(index);
}