We help IT Professionals succeed at work.

Re-ordering a linked list

GPicasso
GPicasso asked
on
Medium Priority
397 Views
Last Modified: 2012-05-12
I think I'm screwing up something conceptually with structs and pointers
Ok so this should build a linked list and then print it..  then reverse it and print it again.
It doesn't do this for some reason.
I appear to be just destroying it or something,  posting relevant code sections

FYI:  The main file here is test.c

Also I'm just starting to learn C.. I always thought that header files were basically the same as C files, they just get included into your code... what's with the separate definitions like you see here?
/* list.c */
        #include "list.h"
        #include <stdlib.h>
        #include "fatal.h"

        /* Place in the interface file */
        struct Node
        {
            ElementType Element;
            Position    Next;
        };

        Position getPrevious(List list, Position end)
        { /*this code has been checked*/
        	Position r = list;
        	while (r->Next != end)
        	{
        		r = r->Next;

        	}
        	return r;

        }
        void
        swapValues(Position headPosition, Position tailPosition)
        { /*this code checks out ok*/
        	ElementType tempElement = 0;
        	tempElement = headPosition->Element;
        	headPosition->Element = tailPosition->Element;
        	tailPosition->Element = tempElement;

        }


        void reverseList( List currentNode)
        {
        	struct Node* previousNode = NULL;
        	struct Node* nextNode = NULL;
        	while (currentNode->Next != NULL)
        	{
        		nextNode = currentNode->Next;
        		currentNode-> Next = previousNode;
        		previousNode = currentNode;
        		currentNode = nextNode;

        	}

        }
        List
       MakeEmpty( List L )
        {
            if( L != NULL )
                DeleteList( L );
            L = malloc( sizeof( struct Node ) );
            if( L == NULL )
                FatalError( "Out of memory!" );
            L->Next = NULL;
            return L;
        }

/* START: fig3_8.txt */
        /* Return true if L is empty */

        int
        IsEmpty( List L )
        {
            return L->Next == NULL;
        }
/* END */

/* START: fig3_9.txt */
        /* Return true if P is the last position in list L */
        /* Parameter L is unused in this implementation */

        int IsLast( Position P, List L )
        {
            return P->Next == NULL;
        }
/* END */

/* START: fig3_10.txt */
        /* Return Position of X in L; NULL if not found */

        Position
        Find( ElementType X, List L )
        {
            Position P;

/* 1*/      P = L->Next;
/* 2*/      while( P != NULL && P->Element != X )
/* 3*/          P = P->Next;

/* 4*/      return P;
        }
/* END */

/* START: fig3_11.txt */
        /* Delete from a list */
        /* Cell pointed to by P->Next is wiped out */
        /* Assume that the position is legal */
        /* Assume use of a header node */

        void
        Delete( ElementType X, List L )
        {
            Position P, TmpCell;

            P = FindPrevious( X, L );

            if( !IsLast( P, L ) )  /* Assumption of header use */
            {                      /* X is found; delete it */
                TmpCell = P->Next;
                P->Next = TmpCell->Next;  /* Bypass deleted cell */
                free( TmpCell );
            }
        }
/* END */

/* START: fig3_12.txt */
        /* If X is not found, then Next field of returned value is NULL */
        /* Assumes a header */

        Position
        FindPrevious( ElementType X, List L )
        {
            Position P;

/* 1*/      P = L;
/* 2*/      while( P->Next != NULL && P->Next->Element != X )
/* 3*/          P = P->Next;

/* 4*/      return P;
        }
/* END */

/* START: fig3_13.txt */
        /* Insert (after legal position P) */
        /* Header implementation assumed */
        /* Parameter L is unused in this implementation */

        void
        Insert( ElementType X, List L, Position P )
        {
            Position TmpCell;

/* 1*/      TmpCell = malloc( sizeof( struct Node ) );
/* 2*/      if( TmpCell == NULL )
/* 3*/          FatalError( "Out of space!!!" );

/* 4*/      TmpCell->Element = X;
/* 5*/      TmpCell->Next = P->Next;
/* 6*/      P->Next = TmpCell;
        }
/* END */

#if 0
/* START: fig3_14.txt */
        /* Incorrect DeleteList algorithm */

        void
        DeleteList( List L )
        {
            Position P;

/* 1*/      P = L->Next;  /* Header assumed */
/* 2*/      L->Next = NULL;
/* 3*/      while( P != NULL )
            {
/* 4*/          free( P );
/* 5*/          P = P->Next;
            }
        }
/* END */
#endif

/* START: fig3_15.txt */
        /* Correct DeleteList algorithm */

        void
        DeleteList( List L )
        {
            Position P, Tmp;

/* 1*/      P = L->Next;  /* Header assumed */
/* 2*/      L->Next = NULL;
/* 3*/      while( P != NULL )
            {
/* 4*/          Tmp = P->Next;
/* 5*/          free( P );
/* 6*/          P = Tmp;
            }
        }
/* END */

        Position
        Header( List L )
        {
            return L;
        }

        Position
        First( List L )
        {
            return L->Next;
        }

        Position
        Advance( Position P )
        {
            return P->Next;
        }

        ElementType
        Retrieve( Position P )
        {
            return P->Element;
        }

Open in new window

/* test.c */
#define NULL 0
#include "list.h"
#include "fatal.h"
#include "stack.h"
#include <stdio.h>
int main()
{
	int i = 0 ;

	List list = MakeEmpty(NULL);


	for (i=1;i<=5; i++)
	{
		Insert(i, list, list);

	}
	printl(list);
	printf("REVERSING\n");


	reverseList(list);
	printl(list);
}
void printl( List list )
{
	while (!IsEmpty(list))
	{
		printf("List element: %d\n", Retrieve(First(list)));
		list = Advance(list);
	}
}

Open in new window

fatal.h
list.h
Comment
Watch Question

CERTIFIED EXPERT

Commented:
First, it appears to be a single linked list.  To be able to reverse it, you should have a doubly linked list.  So each link has two pointers, next and previous.

Author

Commented:
farzanj:  Agreed!  I would love to have a doubly linked list however in this case I'm given a singly linked list... which is also totally reversible , just not as easy to work with.   This is about learning.
Most specifically look at this code here.  It's supposed to be a function for my singly linked list implementation that goes ahead and reverses the pointers of the nodes of the singly linked list.  Leaving the list reversed without actually re-arranging it in physical memory.

Pretty clever... but not too clever because it appears not to work.  Someone please explain away my pointer misconceptions.
Maybe this problem is harder than I thought I'll up the points a little bit

Also I'd still like to know why function signatures go in the header files and then there is a seperate c file with the actual functions (and signatures again.. what is the point of this?)  My textbook set them out this way.

Also I posted two files as code because the mistakes are most likely in those.. the other files are just required for compilation.
/* from list.c */
void reverseList( List currentNode)
        {
        	struct Node* previousNode = NULL;
        	struct Node* nextNode = NULL;
        	while (currentNode->Next != NULL)
        	{
        		nextNode = currentNode->Next;
        		currentNode-> Next = previousNode;
        		previousNode = currentNode;
        		currentNode = nextNode;

        	}

        }

Open in new window

CERTIFIED EXPERT
Awarded 2010
Top Expert 2013

Commented:
I think you just need to add
currentNode->Next = previousNode;
right after the loop (i.e. on line 14)
CERTIFIED EXPERT
Top Expert 2009

Commented:
The problem is because of the confusing use of three different types, that apparently mean the same thing : List, Position and struct Node* are the exact same thing, yet you treat them as if they are different things.

Specifically, when you reverse the linked list, you also "reverse" the start node of the list - ie. the node that is supposed to point to the first node of the linked list. But after reversing, that node has itself become the last node of the linked list, so you've in fact lost the whole linked list, since nothing is pointing to the new start node. If that sounds confusing, that's because it is ;)

The normal way of doing this, is to have a different struct List, that has only a pointer to the start node. When reversing the linked list, take care NOT to treat this as a normal node, but instead make it point to the new start of the linked list (ie. the node that used to be the last node).


>> Also I'd still like to know why function signatures go in the header files and then there is a seperate c file with the actual functions (and signatures again.. what is the point of this?)  My textbook set them out this way.

Please ask that as a separate question. It's unrelated to the reverse issue, and thus should be kept separate.
CERTIFIED EXPERT
Awarded 2010
Top Expert 2013

Commented:
And there are multiple reasons to split the functions into two files.
1: If function f calls function g, then you need to declare g first. But what if they both can call each other? Well, if the prototype (what you are calling the signature) for both comes before the definition of both, then there's no problem.

2: If you forget how to use a function, you don't have to go looking for it. It's all right there in the .h (presumably your function comments are there too).

3: If you build a library to share with others, they can just read the .h and get an idea of how everything works. Also, if you are selling the library, they can't get at the actual code, but they can change any constants and see how the functions are called.

Author

Commented:
Ok guys I'm getting closer, but somehow I'm picking up a zero and losing 1 and 2.  So close, I'm losing my mind to frustration here.

List element: 5
List element: 4
List element: 3
List element: 2
List element: 1
REVERSING
List element: 3
List element: 4
List element: 5
List element: 0

List reverseList( List currentNode)
        { /* After I reverse this list this thing floats off into space */
        	struct Node* previousNode = NULL;
        	struct Node* nextNode = NULL;
        	struct Node* r;

        	while (currentNode->Next != NULL)
        	{
        		r = currentNode;
        		nextNode = currentNode->Next;
        		currentNode-> Next = previousNode;
        		previousNode = currentNode;
        		currentNode = nextNode;

        	}
        	return r;

Open in new window

int main()
{
	int i = 0 ;

	List list = MakeEmpty(NULL);


	for (i=1;i<=5; i++)
	{
		Insert(i, list, list);

	}
	printl(list);
	printf("REVERSING\n");


	list = reverseList(list);
	printl(list);
}

Open in new window

CERTIFIED EXPERT
Awarded 2010
Top Expert 2013

Commented:
Try it like this:
List reverseList( List currentNode)
        {
        	struct Node* nextNode;
          struct Node* previousNode = NULL;

        	while (currentNode != NULL)
        	{
        		nextNode = currentNode-Next;
        		currentNode-> Next = previousNode;
        		previousNode = currentNode;
        		currentNode = nextNode;

        	}
        	return previousNode;

Open in new window

CERTIFIED EXPERT
Awarded 2010
Top Expert 2013

Commented:
It's exactly the same as yours except it goes all the way to the end and returns the right node*

Author

Commented:
Ok part of the problem was simple
i was feeding it [5,4,3,2,1] and getting back [3,4,5,0]  now I'm getting [2,3,4,5,0]  
so close..... what am I not seeing I stepped through the algorithm on paper several times.
List reverseList( List list)
        {
        	Position previousNode = NULL ;
        	Position nextNode =NULL;
        	Position tempNode =NULL;
        	Position currentNode = list;
        	List r;

        	while (currentNode != NULL)
        	{
        		r = currentNode;

        		nextNode = currentNode->Next;
        		currentNode-> Next = previousNode;
        		previousNode = currentNode;
        		currentNode = nextNode;

        	}
        	return r;
        }

Open in new window

CERTIFIED EXPERT
Awarded 2010
Top Expert 2013
Commented:
return previousNode;

Author

Commented:
Man tommy it was working ages ago the last little bug was with my list builder!!! PAINFUL!

Explore More ContentExplore courses, solutions, and other research materials related to this topic.