linked list operation doubt

Jul 20, 2008 at 6:56pm
Hi, I want to write a program using a linked list for storage data of type char. I defined a linked list class and a node struct

I want to read a txt file named "test.txt"(consisting of six characters: C c B b Z z in order) and insert each character into the linked list. After all elements inserted in the list, display the entire list. Then delete the entire list. I should also use toupper function for sorting characters of both upper and lower case.

The following is my code, but I cannot insert the character into the linked list now. I cannot see any contents after calling display function. I still want to know how to add the toupper function in my code to sort upper and lower letters. Any help will be highly appreciated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <fstream>
using namespace std;
class listNode
{
public:
	listNode();   // constructor
	~listNode();  // destructor
	void displayList() const;  // print the contents of the list
	void insert(char );   // insert elemens into the list

private:
	struct Node
	{
		char item;
		Node* nextPtr;
	};
	// pointer to the first node of the list
	Node *head;
};  // end of class listNode

// default constructor
listNode::listNode()
{
	head= NULL;

}

listNode::~listNode()
{
	if(head!=NULL)    // list is not empty
	{
		do
		{
			// declare nodePtr
			Node *nodePtr= head;

			head= head->nextPtr;  // move on to next node
			delete nodePtr;   // delte the node
		} while(head!=NULL); // end do-while 
	} // end if
}  // end destructor

// insert one or more nodes to the list
void listNode::insert(char value)
{
	// get a new node to insert
	Node *newNode;
	Node *nodePtr; // to traverse the list
    Node *previousNode = NULL;  // the previous node
	// allocate a new node 
	newNode= new Node;
	newNode->nextPtr=NULL;
	newNode->item=value;

	if(head=NULL)
	{
		head= newNode;
	    newNode->nextPtr=NULL;
	}
	else
	{
		nodePtr= head;
		previousNode= NULL;
  
		// skip all nodes whose value is less
		while(nodePtr!= NULL)// && (newNode->item> nodePtr->item) )
		{
			previousNode= nodePtr;
			nodePtr= nodePtr->nextPtr;
		}

		if(previousNode==NULL)
		{
			head=newNode;
		    newNode->nextPtr= nodePtr;
		}
		else 
		{
				previousNode->nextPtr= newNode;
				newNode->nextPtr=nodePtr;
        }    // end else-if
	}   // end else-if

}  // end function insert

// print the data in the node
void listNode::displayList() const
{
	if(head==NULL)
	{
		cout<< "\nThe list is empty. ";
		return;
	}

	Node *nodePtr;
	nodePtr= head;
	cout<< "\n\nThe list now contains: ";
	// loop through the whole list
	while(nodePtr!=0)
	{
		// print the list
		cout<<nodePtr->item<<"\n" ;
		// move onto next node of the list
		nodePtr= nodePtr->nextPtr;
	}
}
 

//---------------------------------------------------------------------------------------------------------
int main()
{
	
	cout<< "\n\n\tA program that describes the linked list\n";
	ifstream infile;
	infile.open("simpleTest.txt");
	char ch;
	if(!infile)
	{
		cout<< "Unable to open file simpleTest.txt";
		exit(1);
	}

	listNode mylistNode;
	while(infile)
	{
     infile>> ch;
	 mylistNode.insert(ch);
	}
	mylistNode.displayList();
	infile.close();
	return 0;
}
Last edited on Jul 21, 2008 at 9:49pm
Jul 20, 2008 at 7:31pm
you should try
1
2
string line;
getline(infile,line);

instead of infile>>ch; beause the stream won't doesn't read spaces.
You need to write a functions which separates the caracters from the string after that...
Last edited on Jul 20, 2008 at 7:31pm
Jul 20, 2008 at 10:28pm
Could you explain more clearly? I still don't know how to read all the data into my linked list. By the way, the characters are stored as the format of each line for one character. You said that I need to write a function separating the characters from string. What's this mean?

Update: Now I could only display one element 'b' but I should print all six nodes which are B b C c Z z in order. Anyone can help me?

Thanks.
Last edited on Jul 21, 2008 at 1:03am
Jul 21, 2008 at 3:25pm
Can anybody help me?
Jul 21, 2008 at 7:59pm
First, your design for linked list is not impressive.
At a glance, the listNode is a class/object which each copy/instance of it would have a copy of the list's head.
And each node/object acts as a list where and what to act upon.

I would rather design a container like class that keeps track of the list's head, tail and other list operations. And the node would be a separate struct or class which would just have a data element and linking pointers prev or next.

It would look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

struct Node {
  //by default all public, in a structure
  char item;  // for a single char data element, i would not consider a linked list
  Node *next;

  Node() {}
  Node(char dItem) { item = dItem; next = NULL } 
};

class List {
  public:
    List() { head = NULL; }

    bool insert(char data); // returns true or false, if inserted successfully

    display();  // displays the list in-node or any other traversal 

    bool delete(char data); 

  private:

    Node *head;

    insertList(char data);

    deleteList(char data);

    displayList();
};


As you see it above, the List would be your driver to insert/delete/display the linked list. Just like a container allowing you to operate on and inside the class it takes care of capsulated operations.

And now coming to the data storage, you would have to give your upper/lower case checking within the addList() functionality.
For each node insertion, you would check where the element/node to be placed in the list being created.

It would be like, before you insert check the right place, other you move on to next node. This all would be in a single while loop. It would look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

bool addList(char item)
{ 
  // ...
  if (head == NULL)
     //create a new node, store it as head and return true, if success

   else {
      Node * newItem = new Node(item);
      if (newItem == NULL) //failed allocation
        return false;

     // if list has currently only one item
     if (upper(head->item) > upper(newItem->item)) 
     {
          newItem->next = head;
          head = newItem; 
          return true;
     }

     //otherwise

      Node *current = head;
   
      while (current != NULL)
      {
         if (current->next == NULL && upper(newItem->item) > upper(current->item))   //current is the last in list
         {
               current->next = newItem;
               return true;
          }
         if (upper(current->next->item) > upper(newItem->item) // insert right after current
         {
              newItem->next = current->next;
              current->next  = newItem;
              return true;
          }
 
          //otherwise, keep checking
          current = current->next;
         
      }

   }
}

Hope you understand the point. Check it out.


Good luck :)
Last edited on Jul 21, 2008 at 8:01pm
Jul 21, 2008 at 8:01pm
Line 56: if(head=NULL)
Should be == not =.
Jul 21, 2008 at 9:48pm
Thanks so much for the explanations. I have fixed the problem.
Topic archived. No new replies allowed.