C++

Forum

 
Hello. Need assistance in inserting end of linked list

TheCoolest2 (16)
Hello everyone. I've started data structures this semester, I wasn't expecting to but had a sudden schedule change. I haven't touched c++ in a while so forgive me for making silly mistakes. I've finally gotten time to work on these 2 functions I've been told to finish, insert and intersection l, we are in groups but I cannot wait for group members to get on at 11 pm at night, I have sick family I take care of but I guess they don't care. Anyways so I've been sitting here couple hours trying to do this. I got insert at the front from the lecture a while back and now I've been drawing out the linked list and trying psuedo code for it
Assume we at the root node
Take in data x
Set next to NULL

If the list is not empty, check if the current node has its next set to null. If its not null, travel down the list until its NULL, otherwise set its data to x.
Now forgive me for this sloppy code, I'm in school without a laptop and typing from my phone, ill remember the structure best I can
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
insert(val_type x)
//TODO: implement this function
listNode* temp = root;
listNode* curr;
listNode* newNode;
temp->data = x;
temp->next = NULL;

if(curr->next != NULL) {
    curr->next = newNode;
    newNode = curr;
  }
else {
    curr->data = x;
     }


Yes Im aware its not efficient to insert from the back the professor knows that too but be wants to see if we can figure it out.
I'm not home to test and won't be for another 5 hours so I decided to post. Thanks!

I know this is wrong, I'm not sure where though. Am I even on the right track? I've been on this for days and honestly I feel hopeless ;/
Edit: I'm home now, I'm getting segmentation fault. :/
Last edited on
YFGHNG (319)
Post the entire thing now that you're home. Or at least the entire linked list class you wrote.
Little Captain (206)
If you need help, email me at sparkprogrammer@gmail.com
It will probably be easier than going back and forth via forum posts.
Last edited on
TheCoolest2 (16)
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
 
/******************************************************************
This is the header file for our SORTED linked list class.  We will
implement a singly-linked list that stores its data items in order,
so that walking through the list from the root node to the end will
access data items in increasing order.  We can state things a bit more
formally with a class invariant:

Class invariant: 
1. the root pointer points to the first node in the list, and for 
every other node in the list, the next field of that node points 
to the next node in the list.

2. A node in the list is the last node if and only if it has a null 
next pointer.  Similarly, the list is empty if and only if the root 
pointer is null.

3. Finally, we also require that the list elements are stored in increasing
order, i.e., for any node in the list (call it "Node"), we have that
if Node.next is not null, then (Node.next)->data > Node.data
*********************************************************************/

#pragma once

#include <iostream>
using std::ostream; /* for our operator<< declaration */

namespace csc212
{
	typedef unsigned long val_type;
	/* this typedef statement makes our code a bit more re-usable for other
	 * situations, but it still requires changing the code, re-compiling the
	 * new version, etc...  later on we'll see a better way to do this
	 * (template classes). */

	struct listNode
	{
		/* constructors: */
		listNode();
		listNode(val_type x, listNode* pNext = 0);

		/* data members: */
		val_type data; //the data for the node
		listNode* next; //pointer to the next node in the list
	};

	class list
	{
	public:
		/* constructors: */
		list();
		list(const list& L);

		/* destructor: */
		~list();

		/* operators: */
		list& operator=(const list& L);
		friend bool operator==(const list& L1, const list& L2);
		friend bool operator!=(const list& L1, const list& L2);
		friend ostream& operator<<(ostream& o, const list& L);

		/* member functions to manipulate list: */

		/* pre: none/suff. memory
		 * post: x is inserted (in order) into the list */
		void insert(val_type x);

		/* pre: none
		 * post: x is removed from the list if present */
		void remove(val_type x);

		/* pre: none
		 * post: all items are removed from the list */
		void clear();

		/* pre: none
		 * post: list is unaffected
		 * return: true iff list is empty */
		bool isEmpty();

		/* pre: none
		 * post: list is unaffected
		 * return: boolean that is true iff x was found */
		bool search(val_type x) const;

		/* pre: none
		 * post: list is unaffected
		 * return: length of the list */
		unsigned long length() const;

		/* pre: none, really.  But note that L1 and L2 are assumed to adhere to
		 * part 3 of our class invariant: they should already be sorted.
		 * post: *this is the result of merging L1 and L2, so that it contains
		 * the union of the elements of L1 and L2, in order. */
		void merge(const list& L1, const list& L2);

		/* pre: none
		 * post: the list contains up to n randomly chosen elements in the
		 * range 0..k-1
		 * NOTE: this will only work when val_type is an integer type... */
		void randomFill(unsigned long n, unsigned long k);

		/* pre: none (other than the class invariants)
		 * post: *this will be set to the intersection of L1 and L2 */
		void intersection(const list& L1, const list& L2);

	private:
		listNode* root; /* points to the root.
						   Empty list is described by root == 0 */
	};
}


I haven't made the any of files, they are made by the professor. He assigns the functions he wants us to complete. Above is the header file, I think that's what you all need, but here's the cpp just incase
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
 
/****************************************************
implementation file for linked list class.
*****************************************************/

#include "list.h"
#include <stdlib.h> //for rand()

namespace csc212
{
	/* listNode stuff: */
	listNode::listNode()
	{
		this->next = 0; //set the next pointer to be null
	}

	listNode::listNode(val_type x, listNode *pNext)
	{
		this->data = x;
		this->next = pNext;
	}


	/* linked list implementation: */
	list::list()
	{
		this->root = 0; //initialize the list to be empty
		//remember 0 == NULL, which is never memory you own.
	}

	list::list(const list &L)
	{
		/* TODO: write this. */
		this->root = 0;
	}

	list::~list()
	{
		this->clear(); //delete all nodes, deallocating memory
	}

	list& list::operator=(const list& L)
	{
		/* TODO: write this. */
		return *this;
	}

	bool operator==(const list& L1, const list& L2)
	{

		/* TODO: write this. */
		return false;  //just so it compiles.  you of course need to do something different.
	}
	bool operator !=(const list& L1, const list& L2)
	{
		return !(L1==L2);
	}

	void list::insert(val_type x)	
	{
		// First check if empty, if it is put something in
		// If not empty , check two scenarios
		// Check if current node is last one, if so just assign value
		// If it is not last node, we have to move until we get to the last one
		listNode* start = root;
		listNode* curr;
		listNode* newNode;
		curr->data = x;
		curr->next = NULL;
		
		while(curr->next != NULL) {
			curr = curr->next;
		}
		curr->data = x;

	}

	void list::remove(val_type x)
	{
		/* TODO: write this. */
	}

	bool list::isEmpty()
	{
		return (this->root == 0);
	}

	void list::clear()
	{
		//idea: repeatedly delete the root node...
		listNode* p;
		while((p = root)) //yes, I do mean "=", not "=="
		{
			root = p->next;
			delete p;
		}
	}

	ostream& operator<<(ostream& o, const list& L)
	{
		listNode* p;
		p = L.root;
		while(p)
		{
			o << p->data << " ";
			p = p->next;
		}
		return o;
	}

	bool list::search(val_type x) const
	{
		listNode* p;
		p = root;
		while(p && p->data != x) //again, short circuit evaluation is important...
			p = p->next;
		if(p) 
			return true;
		else 
			return false;
	}

	unsigned long list::length() const
	{
		/* TODO: write this. */
		return 0; //just so it compiles.  you of course need to do something different.
	}

	void list::merge(const list& L1, const list& L2)
	{
		/* TODO: write this. */
		//this algorithm should run in LINEAR TIME and set *this
		//to be the union of L1 and L2, and furthermore the list should remain sorted.
	}

	void list::randomFill(unsigned long n, unsigned long k)
	{
		//we want to fill the list with n random integers from 0..k-1
		this->clear(); //reset to the empty list
		unsigned long i;
		for(i=0; i<n; i++)
		{
			this->insert((val_type)(rand()%k));
		}
	}

	void list::intersection(const list &L1, const list& L2)
	{
		/* TODO: write this. */
		//this algorithm should run in LINEAR TIME, setting *this
		//to be the intersection (ordered) of L1 and L2.
	}
}


I have to do insert and intersection, intersection I believe I've figured out, insert I'm having trouble with. (The other todos my group members are doing, but they are waiting on me cause they need insert to test)
There is a main file that asks questions and based on the letter input, it matches the case and calls a function from list.cpp

As for emailing, I'll try tomorrow thanks
Last edited on
coder777 (8439)
The comments in the insert() function are rather misleading.

To give you the idea how things works:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
	void list::insert(val_type x)	
	{
		
		listNode* newNode = new listNode;
		newNode->data = x;
		newNode->next = NULL;

if(root) // First check if empty
{
		// we have to move until we get to the last one
		listNode* curr = root;
		
		while(curr->next != NULL) { // Check if current node is last one
			curr = curr->next;
		}
		curr->next = newNode;
}
else // if it is put something in
		root = newNode;
	}
TheCoolest2 (16)
Thanks.
So if I understand, we are checking if we are at the root node by doing if(root), meaning theres no data.
If it is, we create a new node called current and make it the root. I don't quite understand why we do this
But the next part I understand (the while loop)
But when we get to curr->next = newNode; Its making the address of the curr node to newNode. Why are we doing that?

and else, root = newNode; So this is saying, if we are not at the root node, we... create a node to put data in?
Topic archived. No new replies allowed.