Why Use a Helper Variable When Inserting an Element in an Array?

  • MHB
  • Thread starter mathmari
  • Start date
  • Tags
    Array
In Summary, We had defined StarS[N] to be an array of lists.)In summary, the programmer wants to write a function for the constitution of a star system. They are wondering how they can insert an element in an array in time complexity O(1). They also want to know what variables they need to use to achieve this. They have done some research and found that setting an element in an "normal" array at a certain index to a value is an O(1) operation, and inserting an element in a linked list (if you already know the location) is also an O(1) operation. They want to write a program for the constitution of a star system "ss". They have also defined
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

How can I insert an element in an array in time complexity O(1)?

What variables do I have to use to achieve this? (Wondering)
 
Technology news on Phys.org
  • #2
mathmari said:
Hey! :eek:

How can I insert an element in an array in time complexity O(1)?

What variables do I have to use to achieve this? (Wondering)

Hi! ;)

Can you clarify what you mean? (Wondering)

Setting an element in an "normal" array at a certain index to a value is an O(1) operation.
And inserting an element in a linked list (if you already know the location) is also an O(1) operation.
 
  • #3
mathmari said:
I want to write a program for the constitution of a star system "ss".

Cool! (Cool)
 
  • #4
I want to write a function for the constitution of a star system "ss".
The new star system contains an empty list of planetary system, that means that in the list of the planetary system exists only the sentinel node, and the empty array of the free-floating planets (ffp). The new star system should be inserted into the array of star systems(StarS). The complexity of the insertion should be $O(1)$.

I have done the following:

Code: 
typedef struct ffplan { 
 int fp;             /*Identifier of the free-floating planet*/
 asteroid_t *ff;     /*Pointer to the first node of the list of the free-floating planets*/
}ffplan_t;  typedef struct starsy { 
 int ss;               /*Identifier of the star system*/
 plansys_t *plasy;     /*Pointer to the first element in the list of the planetary system */
 ffplan_t ffplan[max];     /*The array of the free-floating planets */
 plansys_t *Sentinel;      /*Pointer to the sentinel node of the list of the planetary system */
 int freep;      /*It points to the first free position in the array of the star systems*/ 
}starsy_t;
typedef struct plansys { 
 int solid; 
 asteroid_t *asteroids;   /*Pointer to the first node in the list of the asteroids */
 plansys_t *next;    
}plansys_t; typedef struct asteroid { 
 int as;  
 asteroid_t *prev;      
 asteroid_t *next;       
}asteroid_t;
starsy_t StarS[N];     /*The array of the star systems, it is an array of lists */
 
 int Constitution(int ss) {
	StarS.plasy=StarS.Sentinel;
	StarS.ffplan.fp=INT_MAX;
	StarS.ffplan.ff=NULL;
	return 0;
}

Is it correct so far?? (Wondering)

I haven't understood what is meant by "The new star system should be inserted into the array of star systems(StarS)."

What am I supposed to do?? (Wondering)
 
  • #5
mathmari said:
I haven't understood what is meant by "The new star system should be inserted into the array of star systems(StarS)."

What am I supposed to do?? (Wondering)

It appears that you need to add (or append) the new star system to the array of existing star systems. (Wondering)

Currently your array is N big.
I suppose that is some kind of constant that identifies a maximum.
I think you should track the actual numbers of systems separately.
Say in [m]int nrStarS;[/m]

Then, if you want to add another [m]starsy[/m], you can do:
Code: 
StarS[nrStarS] = starsy;
nrStars++;

This is O(1). (Wasntme)
 
  • #6
I like Serena said:
I think you should track the actual numbers of systems separately.
Say in [m]int nrStarS;[/m]

Couldn't we use for that the field starsy_t.freep, which points to the first free position in the array of the star systems?? (Wondering)
 
  • #7
mathmari said:
Couldn't we use for that the field starsy_t.freep, which points to the first free position in the array of the star systems?? (Wondering)

Well, each "starsy" has that field "freep".
So which one should we use to find the first free position? (Wondering)

And if we add another "starsy", should we update the "freep" field of each of the starsy's? (Wondering)

Or did you mean to implement it as a single linked list? (Wondering)
 
  • #8
I like Serena said:
Well, each "starsy" has that field "freep".
So which one should we use to find the first free position? (Wondering)

And if we add another "starsy", should we update the "freep" field of each of the starsy's? (Wondering)

I don't know... (Worried)

I like Serena said:
Or did you mean to implement it as a single linked list? (Wondering)

Do you mean to implement the array StarS as a single linked list?? (Wondering)
 
  • #9
mathmari said:
Do you mean to implement the array StarS as a single linked list?? (Wondering)

I don't know... (Worried)
Did you?

I suggest to make a choice.
Either StarS is an array for which you track its size so you can easily add another starsy.
Or StarS should be a pointer to a first starsy, and each starsy has a pointer to the next, making it a linked list. (Wasntme)
 
  • #10
I like Serena said:
I don't know... (Worried)
Did you?

I suggest to make a choice.
Either StarS is an array for which you track its size so you can easily add another starsy.
Or StarS should be a pointer to a first starsy, and each starsy has a pointer to the next, making it a linked list. (Wasntme)

We had defined StarS[N] as an array of the star systems, which is an array of lists.

Can we just use StarS as a pointer to a first starsy?? (Wondering)
 
  • #11
mathmari said:
We had defined StarS[N] as an array of the star systems, which is an array of lists.

Can we just use StarS as a pointer to a first starsy?? (Wondering)

Sure. (Nod)

You can use either:
Code: 
int nrStarS = 0;
starsy_t StarS[MAX];
...
StarS[nrStarS++] = starsy;

or:
Code: 
starsy_t *StarS = NULL;
...
starsy->next = StarS;
StarS = starsy.

Both operations are O(1). (Wasntme)
 
  • #12
I like Serena said:
Code: 
starsy_t *StarS = NULL;
...
starsy->next = StarS;
StarS = starsy.

Can we write it in that way although we have defined the Star systems array as a global variable (starsy_t StarS[N]; ) ?? (Wondering)
 
  • #13
mathmari said:
Can we write it in that way although we have defined the Star systems array as a global variable (starsy_t StarS[N]; ) ?? (Wondering)

Nope. (Shake)
 
  • #14
I like Serena said:
Nope. (Shake)

So, that means that I have to insert a starsy in the following way:
Code: 
int nrStarS = 0;
...
StarS[nrStarS++] = starsy;
right?? (Wondering)
 
  • #15
mathmari said:
So, that means that I have to insert a starsy in the following way:
Code: 
int nrStarS = 0;
...
StarS[nrStarS++] = starsy;
right?? (Wondering)

I believe so, yes. (Nod)

That is, unless you're supposed to implement a so called hash map. (Wasntme)
 
  • #16
I like Serena said:
I believe so, yes. (Nod)

That is, unless you're supposed to implement a so called hash map. (Wasntme)

So is the following code also wrong?? (Wondering)

Code: 
int Constitution(int ss) {
	StarS.plasy=StarS.Sentinel;
	StarS.ffplan.fp=INT_MAX;
	StarS.ffplan.ff=NULL;
	return 0;
}
 
  • #17
mathmari said:
So is the following code also wrong?? (Wondering)

Code: 
int Constitution(int ss) {
	StarS.plasy=StarS.Sentinel;
	StarS.ffplan.fp=INT_MAX;
	StarS.ffplan.ff=NULL;
	return 0;
}

It is certainly not consistent with the rest of the code.
The way [m]StarS[/m] is used, implies that it is not an array but a struct of type [m]startsy_t[/m]. (Worried)

Furthermore, [m]ffplan[/m] is also declared as an array, and used here as a struct as well.
 
  • #18
I like Serena said:
It is certainly not consistent with the rest of the code.
The way [m]StarS[/m] is used, implies that it is not an array but a struct of type [m]startsy_t[/m]. (Worried)

Furthermore, [m]ffplan[/m] is also declared as an array, and used here as a struct as well.

From the definition [m]starsy_t StarS[N];[/m] we have that [m]StarS[/m] is an array and also a struct of type [m]startsy_t[/m], right?? (Wondering)

So, is the following correct?? (Wondering)

Code: 
int Constitution(int ss) {
    for(i=0; i<N; i++){
	StarS[i].plasy=StarS.Sentinel;
	StarS[i].ffplan[i].fp=INT_MAX;
	StarS[i].ffplan[i].ff=NULL;
    }
    return 0;
}
 
  • #19
mathmari said:
From the definition [m]starsy_t StarS[N];[/m] we have that [m]StarS[/m] is an array and also a struct of type [m]startsy_t[/m], right?? (Wondering)

So, is the following correct?? (Wondering)

Code: 
int Constitution(int ss) {
    for(i=0; i<N; i++){
	StarS[i].plasy=StarS.Sentinel;
	StarS[i].ffplan[i].fp=INT_MAX;
	StarS[i].ffplan[i].ff=NULL;
    }
    return 0;
}

That is at least syntactically correct. (Nod)

What is the function of the parameter 'ss'? (Wondering)

How much of the code in your earlier post has been given to you? (Wondering)
As it is it won't compile.
 
  • #20
I like Serena said:
That is at least syntactically correct. (Nod)

What is the function of the parameter 'ss'? (Wondering)

How much of the code in your earlier post has been given to you? (Wondering)
As it is it won't compile.

The parameter 'ss' is the identifier of the star system that is constituted.

By "The new star system should be inserted into the array of star systems(StarS)" is maybe meant that we have to insert 'ss' into [m]StarS[].ss[/m] ?? (Wondering) I changed something at the code, and now it compiles...

Code: 
int Constitution(int ss) {
	int nrStarS = 0, i;
	for(i=0; i<N; i++){
		StarS[i].plasy=StarS[i].Sentinel;
		StarS[i].ffplan[i].fp=INT_MAX;
		StarS[i].ffplan[i].ff=NULL;
	}
	StarS[nrStarS++].ss = ss;
	for(i=0; i<nrStarS; i++){
		printf("The elements are: %d \n", StarS[i].ss);
	}
	return 0;
}

int main(){
	Constitution(12);
	return 0;
}
 
  • #21
mathmari said:
The parameter 'ss' is the identifier of the star system that is constituted.

By "The new star system should be inserted into the array of star systems(StarS)" is maybe meant that we have to insert 'ss' into [m]StarS[].ss[/m] ?? (Wondering) I changed something at the code, and now it compiles...

Code: 
int Constitution(int ss) {
	int nrStarS = 0, i;
	for(i=0; i<N; i++){
		StarS[i].plasy=StarS[i].Sentinel;
		StarS[i].ffplan[i].fp=INT_MAX;
		StarS[i].ffplan[i].ff=NULL;
	}
	StarS[nrStarS++].ss = ss;
	for(i=0; i<nrStarS; i++){
		printf("The elements are: %d \n", StarS[i].ss);
	}
	return 0;
}

int main(){
	Constitution(12);
	return 0;
}

It seems to me that the Constitution(ss) function should only initialize 1 star system and not all of them. (Wasntme)
I don't understand the design of your program's data structures, but it seems to me that the function should be something like:

Code: 
int nrStarS = 0;

int Constitution(int ss) {
        int i;

        // Add a star system to the the array of stars
        starsy_t *starsystem = &StarS[nrStarS];
        nrStarS++;

        // Initialize the new star system
        starsystem->ss = ss;
        starsystem->plasy=StarS[i].Sentinel;
	for(i=0; i<max; i++){
		starsystem->ffplan[i].fp=INT_MAX;
		starsystem->ffplan[i].ff=NULL;
	}

        // Return the index of the star system that was added
	return (nrStarS - 1);
}

int main(){
	Constitution(12);
	for(i=0; i<nrStarS; i++){
		printf("The elements are: %d \n", StarS[i].ss);
	}
	return 0;
}
(Thinking)
 
  • #22
I like Serena said:
It seems to me that the Constitution(ss) function should only initialize 1 star system and not all of them. (Wasntme)
I don't understand the design of your program's data structures, but it seems to me that the function should be something like:

Code: 
int nrStarS = 0;

int Constitution(int ss) {
        int i;

        // Add a star system to the the array of stars
        starsy_t *starsystem = &StarS[nrStarS];
        nrStarS++;

        // Initialize the new star system
        starsystem->ss = ss;
        starsystem->plasy=StarS[i].Sentinel;
	for(i=0; i<max; i++){
		starsystem->ffplan[i].fp=INT_MAX;
		starsystem->ffplan[i].ff=NULL;
	}

        // Return the index of the star system that was added
	return (nrStarS - 1);
}

int main(){
	Constitution(12);
	for(i=0; i<nrStarS; i++){
		printf("The elements are: %d \n", StarS[i].ss);
	}
	return 0;
}
(Thinking)

I tried to run it, but I get a segmentation fault... What is the reason?? (Wondering)

When I make into comments the line [m]starsystem->plasy=StarS.Sentinel;[/m] it runs. So, is in this line an error?? (Wondering)
 
Last edited by a moderator:
  • #23
mathmari said:
I tried to run it, but I get a segmentation fault... What is the reason?? (Wondering)

When I make into comments the line [m]starsystem->plasy=StarS.Sentinel;[/m] it runs. So, is in this line an error?? (Wondering)


Yep. (Blush)
It should be: [m]starsystem->plasy=starsystem->Sentinel;[/m].
 
  • #24
At the line [m] starsy_t *starsystem = &StarS[nrStarS];[/m] why do we use & ?? (Wondering)
 
  • #25
mathmari said:
At the line [m] starsy_t *starsystem = &StarS[nrStarS];[/m] why do we use & ?? (Wondering)

The definition [m]starsy_t *starsystem[/m] makes starsystem a pointer, while [m]StarS[nrStarS][/m] is not a pointer, so we cannot assign it. (Shake)

Adding [m]&[/m] in front of it, takes the address of [m]StarS[nrStarS][/m], which is a pointer that we can then assign to [m]starsystem[/m]. (Nod)
 
  • #26
I like Serena said:
The definition [m]starsy_t *starsystem[/m] makes starsystem a pointer, while [m]StarS[nrStarS][/m] is not a pointer, so we cannot assign it. (Shake)

Adding [m]&[/m] in front of it, takes the address of [m]StarS[nrStarS][/m], which is a pointer that we can then assign it to [m]starsystem[/m]. (Nod)

I see... (Smile)
 
  • #27
After that I have to write a function for the constitution of a new object and therefore the constitution of a new planetary system (plansys_t) with identifier of the object "solid" at the star system with identifier "ss". The new planetary system contains an empty list of asteroids. The new element, that corresponds to the new planetary system, should be added to the list of the planetary systems of the star system with identifier "ss".

I have done the following:

Code: 
int Beginning(int solid, int ss){
		int i, k;

        // Add a planetary system to the list of the planetary system of the star system
        plansys_t *plansystem ;
        plansystem->solid=solid;
        plansystem->asteroids=NULL;
		for(i=0; i<nrStarS; i++){
			if(StarS[i].ss=ss){
				k=i;
			}
		}
		StarS[k].plasy=plansystem;
		return k;
}

int main(){
	int k;
	Beginning(8, 12);
	while(StarS[k].plasy != NULL){
		printf(" %d ", StarS[k].plasy->solid);
		StarS[k].plasy=StarS[k].plasy->next;
	}
	return 0;
}

But I get a segmentation fault... What have I done wrong?? (Wondering)
 
  • #28
When you declare [m]plansys_t *plansystem;[/m], you have an uninitialized pointer. That is a pointer that points to some random location.
At its end awaits thee madness and chaos. (Devil)With [m]plansystem->solid=solid;[/m] you follow the pointer to its end and assign it a value. That's when it results in madness and chaos. (Evilgrin)
 
  • #29
I like Serena said:
When you declare [m]plansys_t *plansystem;[/m], you have an uninitialized pointer. That is a pointer that points to some random location.
At its end awaits thee madness and chaos. (Devil)
We want to add a planetary system to the list of the planetary system of the star system, so how could I initialize the pointer?? (Wondering)
 
  • #30
mathmari said:
We want to add a planetary system to the list of the planetary system of the star system, so how could I initialize the pointer?? (Wondering)

We will have to allocate some space for it. (Nod)

In C that is done with [m]malloc()[/m] or [m]calloc()[/m].
For instance:
Code: 
plansys_t *plansystem = calloc(1, sizeof(plansys_t));
It allocates memory for 1 element with the size of the [m]plansys_t[/m] structure.

After this, you can follow the pointer safely. (Angel)
 
  • #31
I like Serena said:
We will have to allocate some space for it. (Nod)

In C that is done with [m]malloc()[/m] or [m]calloc()[/m].
For instance:
Code: 
plansys_t *plansystem = calloc(1, sizeof(plansys_t));
It allocates memory for 1 element with the size of the [m]plansys_t[/m] structure.

After this, you can follow the pointer safely. (Angel)

Ahaa... (Nerd)
I like Serena said:
With [m]plansystem->solid=solid;[/m] you follow the pointer to its end and assign it a value. That's when it results in madness and chaos. (Evilgrin)

Could you explain me further why this is wrong?? (Wondering)
 
  • #32
mathmari said:
Could you explain me further why this is wrong?? (Wondering)

Basically we are talking about a RAM machine.
In a RAM machine we have certain locations of memory available.
And we have an operation to refer to memory indirectly.
However, when we refer to memory indirectly, it always has to refer to a memory location that is actually available.
Otherwise, we have a bad pointer. If we refer to a bad pointer, we will get an access violation, meaning that the pointer does not refer to any valid memory location. (Nerd)
 
  • #33
I like Serena said:
Basically we are talking about a RAM machine.
In a RAM machine we have certain locations of memory available.
And we have an operation to refer to memory indirectly.
However, when we refer to memory indirectly, it always has to refer to a memory location that is actually available.
Otherwise, we have a bad pointer. If we refer to a bad pointer, we will get an access violation, meaning that the pointer does not refer to any valid memory location. (Nerd)

When we call [m]plansys_t *plansystem = calloc(1, sizeof(plansys_t));[/m] has plansystem all the fields of the struct plansys?? So there are the following:
plansystem->solid
plansystem->asteroids
plansystem->next
right?? (Wondering)
 
Last edited by a moderator:
  • #34
mathmari said:
When we call [m]plansys_t *plansystem = calloc(1, sizeof(plansys_t));[/m] has plansystem all the fields of the struct plansys?? So there are the following:
plansystem->solid
plansystem->asteroids
plansystem->next
right?? (Wondering)

Yes. (Nod)

Furthermore, they are all initialized to zero by the calloc() function.
 
  • #35
I like Serena said:
Yes. (Nod)

Furthermore, they are all initialized to zero by the calloc() function.
So, we don't have to add the new object "solid" at the field plansystem->solid , right?? Where do we have to add it then?? (Wondering) I got stuck right now...
 

Similar threads

[BASIC language] Removing an array element -- how?
Replies
32
Views
2K
C# Return type that matches type passed to function in C#
Replies
2
Views
2K
Why are new dimensions added to the left in numpy arrays?
Replies
4
Views
5K
I don't understand my prof's notes relating to time complexity
Replies
7
Views
2K
Python Shifting an array one postion to the left -- Non Function Vs Function
Replies
17
Views
2K
Question about the efficiency of using an array or individual variables
7
Replies
235
Views
12K
C/C++ Question about New syntax of C++
Replies
31
Views
2K
MHB Find First Free Position in Array in $O(\log n)$ Time Complexity
2
Replies
36
Views
6K
MHB Why do we use & before ptr->points?
Replies
2
Views
1K
XOR algorithm to find the missing number in a given array
Replies
13
Views
3K

Hot Threads

Recent Insights

Back
Top