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

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Array
Click For Summary
The discussion centers on the insertion of a new star system into an array of star systems with the goal of achieving O(1) time complexity. Participants clarify that inserting an element at a specific index in an array is O(1), but managing the size of the array requires tracking the number of existing systems. A proposed solution involves using a separate variable to keep track of the number of star systems, allowing for efficient insertion. There is also debate about whether to treat the array as a linked list or maintain it as a fixed-size array. The final consensus suggests initializing only the new star system rather than all systems during insertion.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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
mathmari said:
Hey! :o

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.
 
mathmari said:
I want to write a program for the constitution of a star system "ss".

Cool! (Cool)
 
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)
 
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)
 
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)
 
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)
 
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)
 
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)
 

Similar threads

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