Linked list in C

[MJ]

Hi
I have written a prog for reversing a linked list
I have used globle pointer
Can any one tell me how I can modify this prog so that I dont have to
use extra pointer Head1.
When I reverse a LL using the recursive call how to change the last
node pointer to head and head->next to null without using the extra
global pointer
Mayur



----------------------------------------
//This is the program to create a linkedlist
// and reverse the linkedlist
#include <iostream.h>
#include <malloc.h>
//------------------------------------------
typedef struct node
{
int value;
struct node *next;
}mynode;
//------------------------------------------
//Global Variables
mynode *head,*tail,*temp, *head1;
//------------------------------------------
//Display the contents of the linked list
Display()
{
mynode *temp1;
temp1 = head;
while (temp1) {
cout << temp1->value << "\n";
temp1 = temp1->next;
}
return 0;
}
//------------------------------------------
//Append a node in the linked list
void Add(int value)
{
temp = (mynode *) malloc(sizeof(mynode));
//temp = new mynode;
//temp = (mynode *) malloc(sizeof(mynode*));
temp->value = value;
temp->next = (mynode *)0;
if(head == (mynode *)0) {
head = temp;
}
else
{
mynode *temp1;
temp1 =head;
while(temp1->next != (mynode*)0){
temp1 = temp1->next;
}
temp1->next = temp;
}
}
//------------------------------------------
//Reverse the linked list
mynode * reverse(mynode *ptr)
{
mynode *temp1;
if(!(ptr && ptr->next))
{
head1 = ptr;
return ptr;
}
temp1 = reverse(ptr->next);
temp1->next = ptr;
if(head == ptr)
{
head->next = (mynode*)0;
head = head1;
}
return ptr;
}
//------------------------------------------
//Delete the linked list
void Delete()
{
while(head)
{
mynode *temp;
temp = head;
head = head->next;
free(temp);
//delete temp;

}
}
//------------------------------------------
//Main Program
int main(void)
{
for (int i =1 ; i <= 5; i++) {
Add(i*i*i);
}
Display();
reverse(head);
cout << "--------------------\n";
Display();
//Delete();

// for (i =1 ; i <= 5; i++) {
// Add(i*i*i);
// }
// Display();
// reverse(head);
// cout << "--------------------\n";
// Display();
// Delete();


return 0;
}
//------------------------------------------

 

[Lawrence Kirby]

Hi
I have written a prog for reversing a linked list
I have used globle pointer
Can any one tell me how I can modify this prog so that I dont have to
use extra pointer Head1.
When I reverse a LL using the recursive call how to change the last
node pointer to head and head->next to null without using the extra
global pointer
Mayur

Your first problem is to decide which language you are writing in. You
arew posting to comp.lang.c but your code isn't valid C. If you want to
write C++ code post to comp.lang.c++. What might be considered to be a
good answer to your question could be different there.

Lawrence

 

[Mabden]

Hi
I have written a prog for reversing a linked list
I have used globle pointer
Can any one tell me how I can modify this prog so that I dont have to
use extra pointer Head1.

It's called a doubly-linked list. You have forward and backward links.

 

[CBFalconer]

I have written a prog for reversing a linked list. I have used
globle pointer. Can any one tell me how I can modify this prog
so that I dont have to use extra pointer Head1. When I reverse
a LL using the recursive call how to change the last node pointer
to head and head->next to null without using the extra global
pointer

.... snip off topic C++ code ...

Here is a C package:

/* List handling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#ifndef listops_h_
#define listops_h_

#include <stddef.h> /* NULL */
#include <iso646.h> /* not, and */

/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);

/* ======================================================= */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p);

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void*, void*)); /* compare */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void*, void*)); /* compare */

#endif
/* end listops.h */


/* List handling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#include "listops.h"

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* ======================================================= */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;
} /* splitlist */

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;
} /* mergelists */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */

/* end listops.c */

 

[Stephen Mayes]

... snip off topic C++ code ...

Here is a C package:

/* List handling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#ifndef listops_h_
#define listops_h_

#include <stddef.h> /* NULL */
#include <iso646.h> /* not, and */

/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);

/* ======================================================= */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p);

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void*, void*)); /* compare */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void*, void*)); /* compare */

#endif
/* end listops.h */


/* List handling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#include "listops.h"

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* ======================================================= */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;
} /* splitlist */

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;
} /* mergelists */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */

/* end listops.c */

Good.
Would there be any benefit in making this into a library, rather than just
keeping a copy of the c file around for inclusion in a project?