9 Replies - 341 Views - Last Post: 17 November 2012 - 06:46 PM Rate Topic: -----

#1 PantherFan  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 28-October 12

Linked Lists

Posted 16 November 2012 - 09:54 AM

Is there anyway to create a linked list without using new?
Is This A Good Question/Topic? 0
  • +

Replies To: Linked Lists

#2 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 249
  • View blog
  • Posts: 582
  • Joined: 31-May 11

Re: Linked Lists

Posted 16 November 2012 - 10:04 AM

Sure, you can use malloc(). (But since new can be implemented in terms of malloc() that probably isn't a helpful answer.)
Why do you ask?
Was This Post Helpful? 0
  • +
  • -

#3 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5943
  • View blog
  • Posts: 12,871
  • Joined: 16-October 07

Re: Linked Lists

Posted 16 November 2012 - 12:01 PM

Make a big array and use it for your buffer. While this doesn't really solve the issue of dynamic memory that a linked list is generally used for, it does allow the node pointer thing to work. Instead of a new, you write a function for next available space in the buffer.
Was This Post Helpful? 0
  • +
  • -

#4 PantherFan  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 28-October 12

Re: Linked Lists

Posted 16 November 2012 - 12:21 PM

View PostXupicor, on 16 November 2012 - 10:04 AM, said:

Sure, you can use malloc(). (But since new can be implemented in terms of malloc() that probably isn't a helpful answer.)
Why do you ask?


because i have a program where i cant create allocate new memory because i dont have a default constructor and i cant edit the file so i can create a default constructor. so i have to work around that and figure out a different way.

View Postbaavgai, on 16 November 2012 - 12:01 PM, said:

Make a big array and use it for your buffer. While this doesn't really solve the issue of dynamic memory that a linked list is generally used for, it does allow the node pointer thing to work. Instead of a new, you write a function for next available space in the buffer.


how would i make a big array if i'm using linked list i'm a little confused if possible could you show me an example or explain more if you can?
Was This Post Helpful? 0
  • +
  • -

#5 Xupicor  Icon User is offline

  • Nasal Demon
  • member icon

Reputation: 249
  • View blog
  • Posts: 582
  • Joined: 31-May 11

Re: Linked Lists

Posted 16 November 2012 - 12:35 PM

Wait, are you talking about using std::list, or implementing a list yourself?

If the former, then you can use it with types providing no default constructor - you just have to use it with it in mind. For example, you can't resize it omitting the second parameter of .resize call, as it will then try to use default constructor. When used with the second parameter though, it'll use copy-constructor.
Was This Post Helpful? 0
  • +
  • -

#6 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5943
  • View blog
  • Posts: 12,871
  • Joined: 16-October 07

Re: Linked Lists

Posted 16 November 2012 - 01:41 PM

View PostPantherFan, on 16 November 2012 - 02:21 PM, said:

how would i make a big array if i'm using linked list i'm a little confused if possible could you show me an example or explain more if you can?


What is a linked list, but a value and a pointer to another value? What if you had an array of [il]struct Node { int data, next; };[/code]? The value of next could simply be the index in the array.

e.g.
class List {
public:
	List();
	void add(int);
	void print() const;
	void remove(int);
private:
	static const int ListBuffSize = 100;
	static const int NodeNil = -1;
	struct Node { int data, next; };
	Node items[ListBuffSize];
	int head, avail;
};




View PostPantherFan, on 16 November 2012 - 02:21 PM, said:

because i have a program where i cant create allocate new memory because i dont have a default constructor and i cant edit the file so i can create a default constructor. so i have to work around that and figure out a different way.


If you can get an object instance, you can still use a standard linked list. I don't really follow this.
Was This Post Helpful? 0
  • +
  • -

#7 PantherFan  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 28-October 12

Re: Linked Lists

Posted 16 November 2012 - 08:58 PM

well perhaps it would be easier if i show what im talking about. A lot of the code isnt right because i modified so i could get to run, but ill fix that once i get the problem im describing to you guys fixed first. The error i get is
error: no matching function for call to `Guesser::ListNode::ListNode()'|
 #include "guesser.h"
#include "game.h"

#include <iostream>
#include <fstream>

using namespace std;

const std::string Guesser::alphabet = "abcdefghijklmnopqrstuvwxyz";
 extern int counter;

//ListNode *current;

// Initialize the guesser for a game wit hthe indicated wordlength,
// using words from an indicated file.
Guesser::Guesser (int wordLength, const char* wordListFilename)
{
  for (int i = 0; i < 26; ++i)
    charactersTried[i] = false;

  string word;
  ifstream in (wordListFilename);
  while (in >> word)
    {
      if (word.size() == wordLength)
	{
	  // word is of desired length
	  if (word.find_first_not_of(alphabet) == string::npos) {
	    // word contains only lowercse alphabetics
ListNode *newNode,*head;
ListNode(word,newNode);


//newNode= new ListNode;

//	    possibleSolutions = new possibleSolutions;
newNode= new ListNode;
newNode->data =  word;             // store data(first field)
newNode->next=head;  // store the address of the pointer head(second field)
head = newNode;
	    //word=possibleSolutions->data;
	    cout<<"Here1"<<endl;
	    cout<<"Possible Solutions:"<<newNode->data<<endl;
	    cout<<"Here2"<<endl;
//	    possibleSolutions->next = NULL;
	    //possibleSolutions.push_back (word);
	  }
	}
    }
  in.close();

}


/**
 * Scan the words that are possible solutions so far, counting, for
 * each letter not already tried, the number of words with that letter.
 * Guess the letter that occurs in the most words.
 */
char Guesser::guessACharacter()
{
  int counts[26];
  for (int i = 0; i < 26; ++i)
    counts[i] = 0;

  // Count the number of words in which each letter can be found
  while(possibleSolutions!=NULL)
    {
     // string word = possibleSolutions[i];
    // string* word;
    possibleSolutions=possibleSolutions->next;//needs to be fixed
      for (char c = 'a'; c <= 'z'; ++c)
	{
	  if (!charactersTried[c- 'a'])
	    {
	      // Character c has not been tried yet
//	      if (possibleSolutions.find(c) != string::npos) needs to be fixed
		// c is in this word
		++counts[c - 'a'];
	    }
	}
    }

  // Find the character that occurs in the most words
  char guess = ' ';
  int maxSoFar = -1;
  for (char c = 'a'; c <= 'z'; ++c)
    {
      if (counts[c - 'a'] > maxSoFar)
	{
	  guess = c;
	  maxSoFar = counts[c - 'a'];
	}
    }


  if (maxSoFar <= 0)
    {
      guess = 'a';
      while (charactersTried[guess-'a'])
	++guess;
    }

  charactersTried[guess-'a'] = true;
  return guess;
}


/**
 * Following a successful guess of a letter in the word, make a pass through
 * the possibleSolutions, removing all words that do not contain the
 * guess character in the positions indicated in wordSoFar.
 */
void Guesser::characterIsInWord (char guess, const string& wordSoFar)
{
//  vector<string> remainingSolutions;
  while(possibleSolutions!=NULL)
    {
//      string wd = possibleSolutions[i];//needs to be fixed
      bool OK = true;
      for (int k = 0; OK && k < wordSoFar.size(); ++k)
	{
	  if (wordSoFar[k] == guess)
	    {
//	      if (wd[k] != guess)//needs to be fixed
		{
		  OK = false;
		}
	    }
	}
      if (OK)
	{
	  //cerr << "Keeping " << wd << endl;
	  //remainingSolutions.push_back (wd);
//	   ListNode<possibleSolutions->data>* newNode = new LListNode<Data>(wd, NULL);
  }

	}

//  possibleSolutions = remainingSolutions;

}


/**
 * Following a mistaken guess of a letter in the word, make a pass through
 * the possibleSolutions, removing all words that contain the
 * guess character.
 */
void Guesser::characterIsNotInWord (char guess)
{
ListNode* remainingSolutions;
string wd;
  while(possibleSolutions!=NULL)
    {
       possibleSolutions->data=wd;
      if (wd.find(guess) == string::npos)
	{
	  remainingSolutions->data;
	}
    }
  possibleSolutions = remainingSolutions;
}


/**
 * Guesser has lost the game. Look at the provider's actual word
 * and gripe a bit about losing.
 */
void Guesser::admitToLoss (std::string actualWord, const string& wordSoFar)
{
  bool match = actualWord.size() == wordSoFar.size();
  for (int i = 0; match && i < actualWord.size(); ++i)
    {
      match = wordSoFar[i] == Game::FILL_CHARACTER ||
	wordSoFar[i] == actualWord[i];
    }
  if (!match)
    {
      cout << "Ummm...your word '" << actualWord
	   << "' does not match the patterh '"
	   << wordSoFar <<"'.\nDid you make a mistake somewhere?"
	   << endl;
    }
  else
    {
      for (int i = 0; match && i < actualWord.size(); ++i)
	{
	  if (wordSoFar[i] == Game::FILL_CHARACTER
	      && charactersTried[actualWord[i]-'a'])
	    {
	      cout << "Did you forget to mention the '"
		   << actualWord[i]
		   << "' in position " << i+1 << "?"
		   << endl;
	      return;
	    }
	}

      for (int i = 0; (!match) && possibleSolutions !=NULL; ++i)
	match = (actualWord == possibleSolutions->data);
	possibleSolutions=possibleSolutions->next;
//      match = match && (counter > 0);//Needs th be fixed
      if (match)
	{
	  cout << "OK, I might have guessed that eventually." << endl;
	}
      else
	{
	  cout << "Interesting, I don't know that word. Are you sure you\n"
	       << "spelled it correctly?." << endl;
	}

    }
}



Now for the header file.
#ifndef GUESSER_H
#define GUESSER_H

#include <string>


class Game;

class Guesser {
public:
  // Initialize the guesser for a game with the indicated wordlength,
  // using words from an indicated file.
  Guesser (int wordLength, const char* wordListFilename);


  /**
   * Scan the words that are possible solutions so far, counting, for
   * each letter not already tried, the number of words with that letter.
   * Guess the letter that occurs in the most words.
   */
  char guessACharacter();


  /**
   * Following a successful guess of a letter in the word, make a pass through
   * the possibleSolutions, removing all words that do not contain the
   * guess character in the positions indicated in wordSoFar.
   */
  void characterIsInWord (char guess, const std::string& wordSoFar);


  /**
   * Following a mistaken guess of a letter in the word, make a pass through
   * the possibleSolutions, removing all words that contain the
   * guess character.
   */
  void characterIsNotInWord (char guess);


  /**
   * Guesser has lost the game. Look at the provider's actual word
   * and gripe a bit about losing.
   */
  void admitToLoss (std::string actualWord, const std::string& wordSoFar);
private:

  struct ListNode {
    std::string data;
    ListNode* next;

    ListNode (std::string str, ListNode* nxt)
      :data(str), next(nxt)
    { // data=str; next=nxt;
    }
  };

  // A collection of words that match all guesses made so far
  ListNode* possibleSolutions;
//typedef Guesser possibleSolutions;
  // Tracks characters already guessed.
  //  charactersTried[c-'a'] is true if the character c
  //    has been guessed previously
  bool charactersTried[26];

  static const std::string alphabet;


  // For grading purposes - Ignore this (but don't remove it)
  friend void instructorCheck (const Guesser& g);

};


#endif


Was This Post Helpful? 0
  • +
  • -

#8 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1112
  • View blog
  • Posts: 4,619
  • Joined: 09-June 09

Re: Linked Lists

Posted 16 November 2012 - 09:19 PM

A pointer can point wherever you want. Pointing node pointers on the stack is not much different from pointing them on the run time heap. Create a large buffer and point your "next" pointers into that buffer.

Here is a simple example
#include <iostream>

#define KILOBYTE 1024

struct Node {
   int data;
   Node *next;
};

class LinkedList {
   Node *head;
   char buffer[KILOBYTE];

public:
   LinkedList(): head(0) {
      memset(buffer, 0, KILOBYTE);
   }

   void add(int data) {
      if(!head) {
         head = (Node*)buffer;
         head->data = data;
      }
      else {
         Node *temp = head;
         while(temp->next != 0) 
            temp=temp->next;

         temp->next = temp + sizeof(Node);
         temp->next->data = data;
      }
   }

   void print() {
      Node *temp = head;
      while(temp) {
         std::cout<<temp->data<<std::endl;
         temp = temp->next;
      }
   }
};

int main()
{
   LinkedList list;
   list.add(10);
   list.add(20);
   list.add(30);
   list.print();

   std::cin.ignore();
   std::cin.get();
   return 0;
}



The only issue with allocating your linked list on the stack is you need to know the maximum number of nodes you can have possible in your list. In the code above I chose a kilobyte worth of data which translates to 128 nodes.

#nodes = 1024 / (sizeof(int) + sizeof(Node*))
#nodes = 1024 / (4 + 4) = 1024 / 8 = 128

This post has been edited by jjl: 16 November 2012 - 09:27 PM

Was This Post Helpful? 0
  • +
  • -

#9 PantherFan  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 11
  • Joined: 28-October 12

Re: Linked Lists

Posted 17 November 2012 - 09:14 AM

the error appears at 037 by the way, in the cpp file. But i have never seen define kilobyte before wo i can try that.
Was This Post Helpful? 0
  • +
  • -

#10 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1112
  • View blog
  • Posts: 4,619
  • Joined: 09-June 09

Re: Linked Lists

Posted 17 November 2012 - 06:46 PM

Quote

But i have never seen define kilobyte before wo i can try that.


That is just a preprocessor definition, it can be replaced with a const integer (that would be more C++ style anyways).

#include <iostream>

const int KILOBYTE = 1024;

struct Node {
   int data;
   Node *next;
};

class LinkedList {
   Node *head;
   char buffer[KILOBYTE];

public:
   LinkedList(): head(0) {
      memset(buffer, 0, KILOBYTE);
   }

   void add(int data) {
      if(!head) {
         head = (Node*)buffer;
         head->data = data;
      }
      else {
         Node *temp = head;
         while(temp->next != 0) 
            temp=temp->next;

         temp->next = temp + sizeof(Node);
         temp->next->data = data;
      }
   }

   void print() {
      Node *temp = head;
      while(temp) {
         std::cout<<temp->data<<std::endl;
         temp = temp->next;
      }
   }
};

int main()
{
   LinkedList list;
   list.add(10);
   list.add(20);
   list.add(30);
   list.print();

   std::cin.ignore();
   std::cin.get();
   return 0;
}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1