10 Replies - 9580 Views - Last Post: 22 September 2011 - 08:00 PM Rate Topic: -----

#1 BleuCheese  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 24
  • Joined: 11-September 11

Inserting data into a sorted linked list

Posted 21 September 2011 - 07:25 PM

Hey guys,

I wrote code for a linked list and it works perfectly fine but now I'm trying to write code that takes integer data and places in the linked list in a sorted fashion. Can anyone tell me what I may be doing wrong? It just continues to run and never terminates when I run the test I wrote.

addSorted Function
void addSorted(Data * newData){
	  if(head == NULL){
		  head = new LinkNode(newData);
	  }
	  else{
		  if (newData < head->data){
			  LinkNode * current = head;
			  head = new LinkNode(newData);
			  head->data = newData;
			  head->next = current;
		  }
		  else{
			  LinkNode * current = head;
			  LinkNode * previous = head;
			  while (current != NULL){
				if (newData < current->data){
					previous->next = new LinkNode();
					previous = previous->next;
					previous->data = newData;
					previous->next = current;
				}
				else if (current->next == NULL){
					current->next = new LinkNode();
					current = current->next;
					current->data = newData;
					current->next = NULL;
				}
				else {
					previous = current;
					current = current->next;
				}
			  }
		  }
	  }
  }




Test Function
void testLinkedListAddSorted() {
	LinkedList * testList = new LinkedList();
	IntegerData * data5 = (IntegerData *)testList->get(5);
	IntegerData * data13 = (IntegerData *)testList->get(13);
	IntegerData * data12 = (IntegerData *)testList->get(12);

	for (int i = 0; i < 10; i++){
		testList->addSorted(new IntegerData(i));
	}

	    cout << testList->toString() << endl;
	    testList->addSorted(data5);
	    cout << testList->toString() << endl;
	    testList->addSorted(data13);
	    cout << testList->toString() << endl;
	    testList->addSorted(data12);
	    cout << testList->toString() << endl;

	    // clean up memory
	    for (int i = 0; i < testList->size(); i++) {
	      delete testList->get(i);
	    }
	    // now delete the data structure
	    delete testList;
}



Is This A Good Question/Topic? 0
  • +

Replies To: Inserting data into a sorted linked list

#2 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1156
  • View blog
  • Posts: 2,538
  • Joined: 05-May 05

Re: Inserting data into a sorted linked list

Posted 21 September 2011 - 08:00 PM

if (newData < head->data){
07	              LinkNode * current = head;
08	              head = new LinkNode(newData);
09	              head->data = newData;
10	              head->next = current;
11	          }



Why are you setting the data twice? Also, if your starting your search at the head of the list, then what's the point of checking the head before you enter the loop. That's duplicate code.

Here's something that should be about right. I didn't test it though.

void addSorted(Data* newData) 
{
    //sole node in list
    if(!head) {
        head = new LinkNode(newData);
        return;
    }
    //append inside list
    LinkNode* curr = head, *prev = NULL;
    while(curr) {
        //found insertion position
        if(newData < curr->data) {
            LinkNode* newNode = new LinkNode(newData);
            //put new node in behind the node we're looking at
            newNode->next = curr;
            //if we're looking at the head, make new node the head
            if(!prev) {
                head = newNode;
            }else {
                //put new node in front of the 'previous' node
                prev->next = newNode;
            }
            return;
        }
        prev = curr;
        curr = curr->next;
    }
    //append to end list
    prev->next = new LinkNode(newData);
}


This post has been edited by blackcompe: 21 September 2011 - 08:04 PM

Was This Post Helpful? 1
  • +
  • -

#3 BleuCheese  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 24
  • Joined: 11-September 11

Re: Inserting data into a sorted linked list

Posted 21 September 2011 - 10:09 PM

I changed around some things and got rid of the double data assignment also. The code is working now but for some odd reason when I remove a 0 from the front of the linked list and try to place it back in, it returns the 0 in front of the 1.

[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]

  void addSorted(Data* newData){
      if(head == NULL) {
          head = new LinkNode(newData);
      }
      LinkNode * current = head;
      LinkNode * previous = NULL;
      while(current != NULL) {
          if(newData < current->data) {
              LinkNode * newNode = new LinkNode(newData);
              newNode->next = current;
              if(previous != NULL) {
                  head = newNode;
              }
              else {
                  previous->next = newNode;
              }
          return;
          }
      previous = current;
      current = current->next;
      }
  previous->next = new LinkNode(newData);
  }


Was This Post Helpful? 0
  • +
  • -

#4 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1156
  • View blog
  • Posts: 2,538
  • Joined: 05-May 05

Re: Inserting data into a sorted linked list

Posted 21 September 2011 - 10:27 PM

That's because of this:

if(previous != NULL) {


It should be if previous is null.

if(!previous)


That says: "if previous is null."

Also, you should have a return statement in the first if statement, or else your function won't be correct. If you attempt to insert a value into an empty list, I think the value will be inserted twice.

This post has been edited by blackcompe: 21 September 2011 - 10:28 PM

Was This Post Helpful? 1
  • +
  • -

#5 BleuCheese  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 24
  • Joined: 11-September 11

Re: Inserting data into a sorted linked list

Posted 21 September 2011 - 10:39 PM

Yeah, I tried both of those things and neither of them corrected my problem. Hmmmmm, this makes me think. There has to be another condition that isn't holding true somewhere in the code, or maybe a special case that needs to be added?
Was This Post Helpful? 0
  • +
  • -

#6 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1156
  • View blog
  • Posts: 2,538
  • Joined: 05-May 05

Re: Inserting data into a sorted linked list

Posted 21 September 2011 - 10:45 PM

So you changed:

if(previous != NULL) {


to:

if(previous == NULL) {


any it still didn't work? That's almost unbelievable. Given your remove method works correctly, and your list is [1, 2, 3], I guarantee addSorted(0) will put the 0 at the head of the list.
Was This Post Helpful? 1
  • +
  • -

#7 BleuCheese  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 24
  • Joined: 11-September 11

Re: Inserting data into a sorted linked list

Posted 21 September 2011 - 10:53 PM

Yeah, it's quite odd and I'm positive my remove method works correctly. I'm going to repaste my test case that I wrote. Maybe there is something odd going on there that I'm not seeing.

void testLinkedListAddSorted() {
    LinkedList * testList = new LinkedList();

    // TEST add
    for (int i = 0; i < 10; i++) {
      testList->add(new IntegerData(i));
    }

    for (int i = 0; i < 10; i++) {
      IntegerData * data = (IntegerData *)testList->get(i);
      if (data == NULL || data->value != i) {
        cout << "Error: data at index " << i << " is not == " << i << endl;
      }
    }

    cout << testList->toString() << endl;

    IntegerData * data5 = (IntegerData *)testList->get(5);
       if (data5 != NULL) {
         testList->remove(data5);
         cout << testList->toString() << endl;
       }

    testList->addSorted(data5);
    cout << testList->toString() << endl;

    IntegerData * data9 = (IntegerData *)testList->get(9);
       if (data9 != NULL)
         testList->remove(data9);
         cout << testList->toString() << endl;


    testList->addSorted(data9);
    cout << testList->toString() << endl;


    IntegerData * data0 = (IntegerData *)testList->get(0);
    testList->remove(data0);
    cout << testList->toString() << endl;

    testList->addSorted(data0);
    cout << testList->toString() << endl;


    // clean up memory
    for (int i = 0; i < testList->size(); i++) {
      delete testList->get(i);
    }
    // now delete the data structure
    delete testList;
}



And this is what always prints out:

Testing LinkedList addSorted functions...
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
Was This Post Helpful? 0
  • +
  • -

#8 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1156
  • View blog
  • Posts: 2,538
  • Joined: 05-May 05

Re: Inserting data into a sorted linked list

Posted 21 September 2011 - 11:18 PM

If you want post your entire code, I'll take a quick look at it.
Was This Post Helpful? 0
  • +
  • -

#9 BleuCheese  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 24
  • Joined: 11-September 11

Re: Inserting data into a sorted linked list

Posted 22 September 2011 - 09:54 AM

#ifndef LINKED_LIST_
#define LINKED_LIST_

#include <iostream>
#include <cmath>
#include <string>
#include <sstream>

using std::string;
using std::stringstream;

#include "Collection.h"
#include "Stack.h"

using std::cout;
using std::endl;

#ifndef NULL
#define NULL 0
#endif

struct LinkNode {
  Data * data;
  LinkNode * next;
  LinkNode(Data * data = NULL, LinkNode * next = NULL) : data(data), next(next) {}
};

class LinkedList : Collection{
  LinkNode * head;

public:
  LinkedList() {
    this->head = NULL;
  }

  ~LinkedList() {
    LinkNode * current = head;
    while (current != NULL) {
      LinkNode * next = current->next;
      delete current;
      current = next;
    }
  }

  void addSorted(Data* newData){
      if(head == NULL) {
          head = new LinkNode(newData);
          return;
      }
      LinkNode * current = head;
      LinkNode * previous = NULL;
      while(current != NULL) {
          if(newData < current->data) {
              LinkNode * newNode = new LinkNode(newData);
              newNode->next = current;
              if(previous == NULL) {
                  head = newNode;
              }
              else {
                  previous->next = newNode;
              }
          return;
          }
      previous = current;
      current = current->next;
      }
  previous->next = new LinkNode(newData);
  }

  void addSorted(LinkedList * newLinkedList){

  }

  int size() const {
    LinkNode* current = head;
    int count = 0;
    while (current != NULL) {
      count++;
      current = current->next;
    }
    return count;
  }

  void insert(Data * newData) {
    LinkNode * newNode = new LinkNode(newData);
    newNode->next = head;
    head = newNode;
  }

  void add(Data * newData) {
    if (head == NULL) {
      head = new LinkNode(newData);
    }
    else {
      LinkNode * current = head;
      while (current->next != NULL) {
        current = current->next;
      }

      current->next = new LinkNode(newData);
    }
  }

  bool remove(Data * d) {
    LinkNode * current = head;
    LinkNode * previous = NULL;
    while (current != NULL && current->data != d) {
      previous = current;
      current = current->next;
    }
    if (current != NULL) {
      if (previous == NULL) {
        head = current->next;
      }
      else {
        previous->next = current->next;
      }
      delete current;

      return true;
    }
    else {
      return false;
    }

  }

  bool member(Data * d) {
    LinkNode * current = head;
    while (current != NULL && current->data->compareTo(d) != 0) {
      current = current->next;
    }
    return current != NULL;
  }

  Data * get(int index) {
    LinkNode* current = head;
    if (index >= size()) {
      return NULL;
    }
    int count = 0;
    while (current != NULL && count < index) {
      count++;
      current = current->next;
    }
    return current->data;
  }

  string toString() const {
    stringstream s;

    s << "[";
    LinkNode* current = head;
    if (current != NULL) {
      s << current->data->toString();
      current = current->next;
      while (current != NULL) {
        s << ", " << current->data->toString();
        current = current->next;
      }
    }
    s << "]";
    return s.str();
  }

};
#endif /* LINKED_LIST_ */


This post has been edited by BleuCheese: 22 September 2011 - 09:57 AM

Was This Post Helpful? 0
  • +
  • -

#10 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1156
  • View blog
  • Posts: 2,538
  • Joined: 05-May 05

Re: Inserting data into a sorted linked list

Posted 22 September 2011 - 02:13 PM

This code works perfectly. I had to create my own Data class since you didn't include yours, so I'm wondering if your problem lays there.

Posted Image

#include <iostream>
#include <cmath>
#include <string>
#include <sstream>
 
using std::string;
using std::stringstream;
 
using std::cout;
using std::endl;
 
class Data
{
public:
    int value;
    Data(int n): value(n) {}
    bool operator< (Data d) {
        return value < d.value;
    }
    bool operator> (Data d) {
        return value > d.value;
    }
    string toString() {
        stringstream ss;
        ss << value;
        return string(ss.str());
    }
};
 
struct LinkNode {
    Data * data;
    LinkNode * next;
    LinkNode(Data * data = NULL, LinkNode * next = NULL) : data(data), next(next) {}
};
 
class LinkedList
{
    LinkNode * head;
 
public:
    LinkedList() {
        this->head = NULL;
    }
 
    ~LinkedList() {
        LinkNode * current = head;
        while (current != NULL) {
            LinkNode * next = current->next;
            delete current;
            current = next;
        }
    }
 
    void addSorted(Data* newData) {
        if(head == NULL) {
            head = new LinkNode(newData);
            return;
        }
        LinkNode * current = head;
        LinkNode * previous = NULL;
        while(current != NULL) {
            if(newData < current->data) {
                LinkNode * newNode = new LinkNode(newData);
                newNode->next = current;
                if(previous == NULL) {
                    head = newNode;
                } else {
                    previous->next = newNode;
                }
                return;
            }
            previous = current;
            current = current->next;
        }
        previous->next = new LinkNode(newData);
    }
 
    void addSorted(LinkedList * newLinkedList) {
 
    }
 
    int size() const {
        LinkNode* current = head;
        int count = 0;
        while (current != NULL) {
            count++;
            current = current->next;
        }
        return count;
    }
 
    void insert(Data * newData) {
        LinkNode * newNode = new LinkNode(newData);
        newNode->next = head;
        head = newNode;
    }
 
    void add(Data * newData) {
        if (head == NULL) {
            head = new LinkNode(newData);
        } else {
            LinkNode * current = head;
            while (current->next != NULL) {
                current = current->next;
            }
 
            current->next = new LinkNode(newData);
        }
    }
 
    bool remove(Data * d) {
        LinkNode * current = head;
        LinkNode * previous = NULL;
        while (current != NULL && current->data != d) {
            previous = current;
            current = current->next;
        }
        if (current != NULL) {
            if (previous == NULL) {
                head = current->next;
            } else {
                previous->next = current->next;
            }
            delete current;
 
            return true;
        } else {
            return false;
        }
 
    }
 
    Data * get(int index) {
        LinkNode* current = head;
        if (index >= size()) {
            return NULL;
        }
        int count = 0;
        while (current != NULL && count < index) {
            count++;
            current = current->next;
        }
        return current->data;
    }
 
    string toString() const {
        stringstream s;
 
        s << "[";
        LinkNode* current = head;
        if (current != NULL) {
            s << current->data->toString();
            current = current->next;
            while (current != NULL) {
                s << ", " << current->data->toString();
                current = current->next;
            }
        }
        s << "]";
        return s.str();
    }
 
};
 
 
void testLinkedListAddSorted()
{
    LinkedList * testList = new LinkedList();
 
    // TEST add
    for (int i = 0; i < 10; i++) {
        testList->add(new Data(i));
    }
 
    for (int i = 0; i < 10; i++) {
        Data * data = (Data *)testList->get(i);
        if (data == NULL || data->value != i) {
            cout << "Error: data at index " << i << " is not == " << i << endl;
        }
    }
 
    cout << testList->toString() << endl;
 
    Data * data5 = (Data *)testList->get(5);
    if (data5 != NULL) {
        testList->remove(data5);
        cout << testList->toString() << endl;
    }
 
    testList->addSorted(data5);
    cout << testList->toString() << endl;
 
    Data * data9 = (Data *)testList->get(9);
    if (data9 != NULL)
        testList->remove(data9);
    cout << testList->toString() << endl;
 
 
    testList->addSorted(data9);
    cout << testList->toString() << endl;
 
 
    Data * data0 = (Data *)testList->get(0);
    testList->remove(data0);
    cout << testList->toString() << endl;
 
    testList->addSorted(data0);
    cout << testList->toString() << endl;
 
 
    // clean up memory
    for (int i = 0; i < testList->size(); i++) {
        delete testList->get(i);
    }
    // now delete the data structure
    delete testList;
}
 
 
 
int main()
{
    testLinkedListAddSorted();
}


Was This Post Helpful? 0
  • +
  • -

#11 BleuCheese  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 24
  • Joined: 11-September 11

Re: Inserting data into a sorted linked list

Posted 22 September 2011 - 08:00 PM

I made my data class within the .cpp file I sent. Otherwise, the only other thing I have is a collection header file that has my data class with just pure virtual functions in it.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1