Thread: Arrays insertion/deletion linear?

1. Arrays insertion/deletion linear?

So, I understand why arrays have fast random access(Searching) or constant time access for searching, because you have an index and you just say goto array[index]. Example array[5]. But im not quite understanding why insertion/deletion of indexes is linear and not constant? Wouldn't it be the same thing? You just say array[5] delete. and it jumps right to that index and deletes it? My understanding is that linear means it has to run through the whole array to get to the index you specified..? So when you say insertions/deletions are linear for arrays im wondering why do you have to linearly go through all the indexes that precede the index you are referring to to get to the one you are referring to? It is an array you should just specify the index to delete and it jumps right to it in constant time and deletes it, correct? Anyways just trying to clear this up. Im not saying its not linear and I totally believe it is, I just cant put my finger on the details of how it is linear for insertion/deletion. Thanks in advance for your responses. Try not to flame me to much, as im sure the explanation for this is quite simple.

2. It's not finding the element that's hard, it's moving element 6 down to slot 5, and element 7 down to slot 6, and element 8 down to slot 7, ..., ..., ..., and element 100 down to slot 99 that can take some time.

(That assumes that your "array" is supposed to heal up when you delete something from the middle.)

3. Ahhh..... So this really applies to like an Arraylist say in java, that can flex. I.E its like an array without a specified size so when you delete something it shrinks and when you add something it grows. For a regular array that has its size specified this would not apply? Because you wouldn't actually be shrinking or growing the array. Technically you dont insert/delete on a regular array I guess you really just change the values at the specified index but the size is set so you cannot shrink it or grow it.

4. Right. This would certainly apply even more so to insertion, as in a real array you can never insert in the middle (except in the logical sense of moving all the current data up a spot and putting the new data in place).

The C++ equivalent would be vector.

5. Awesome, Thanks for the help. Glad I got that straightened out. Its was really bothering me

6. Originally Posted by jakemott
Ahhh..... So this really applies to like an Arraylist say in java, that can flex. I.E its like an array without a specified size so when you delete something it shrinks and when you add something it grows. For a regular array that has its size specified this would not apply? Because you wouldn't actually be shrinking or growing the array. Technically you dont insert/delete on a regular array I guess you really just change the values at the specified index but the size is set so you cannot shrink it or grow it.
Yeah that's about it.

Personally I can't stand the name "ArrayList".
An Array has contant time indexing and linear time removal. A list has linear time indexing and constant time removal. The two couldn't be more different, so which is it dammit! It's like they named it to intentionally make newbies not care about the very important differences between container types.

7. It's named after the abstract data type linear list, which is what C++ calls a sequence.

8. Originally Posted by CornedBee
It's named after the abstract data type linear list, which is what C++ calls a sequence.
I thought C++ called a linear list a "list".

9. Originally Posted by tabstop
I thought C++ called a linear list a "list".
Why would a std::list be linear? Each node of the list could be anywhere in memory at all, the opposite of "linear"

10. Originally Posted by brewbuck
Why would a std::list be linear? Each node of the list could be anywhere in memory at all, the opposite of "linear"
I've never come across any definition of a linear list that required consecutive data storage, merely a way to get to "next". If you have one, please share.

11. Originally Posted by tabstop
I've never come across any definition of a linear list that required consecutive data storage, merely a way to get to "next". If you have one, please share.
I don't know if there is some accepted meaning for this terminology. But I do know what "linear" means. As far as being able to get the next element, what use is a list if you can't? That either renders the word "linear" redundant, or linear must mean something else. To me, linear means organized linearly in memory.

12. Originally Posted by brewbuck
I don't know if there is some accepted meaning for this terminology. But I do know what "linear" means. As far as being able to get the next element, what use is a list if you can't? That either renders the word "linear" redundant, or linear must mean something else. To me, linear means organized linearly in memory.
You may be the only one. But who among us has not done, if you'll forgive the C in a C++ forum:
Code:
```struct node {
int data;
struct node *next;
};```
at least once in our lives? A quite simple linear list (as opposed to a tree or some other nonlinear structure), providing for easy insertion and deletion, and a way to get to next without requiring contiguous memory, albeit at the cost of losing random access.

13. Originally Posted by tabstop
You may be the only one. But who among us has not done, if you'll forgive the C in a C++ forum:
Code:
```struct node {
int data;
struct node *next;
};```
at least once in our lives? A quite simple linear list (as opposed to a tree or some other nonlinear structure), providing for easy insertion and deletion, and a way to get to next without requiring contiguous memory, albeit at the cost of losing random access.
I don't think the difference between a tree and a list is "linearity," but rather the fact that a tree... is a tree. And a list... is a list. "Linear" seems redundant, or at least the wrong term to specify the difference.

14. My thought process for this is. Linear meaning to get from point A to point B you have to go to every point in between A and B. I.E. To get to a specific node(Search/random access) in a list you would have to traverse the entire List(Unless you had pointers to nodes in the middle and elsewhere) from the start(A) to the specified node (B) which would be a linear(Straight) path. But if you wanted to insert into the List you just insert at the end so you dont have to traverse the List it would just be constant time not Linear time. The reason why a tree isnt linear is because your not really taking a straight path from node A to node B. You may take the left branch from the root them from there take the right branch etc etc in the end you took a curving non-linear path. You didn't necessarily have to visit every point in Between point A and B. Since a tree has branches you may have skipped points that you would have had to visit in a linear list to get to point B.

15. Originally Posted by brewbuck
I don't think the difference between a tree and a list is "linearity," but rather the fact that a tree... is a tree. And a list... is a list. "Linear" seems redundant, or at least the wrong term to specify the difference.
And a dog ... is a dog, and a cat ... is a cat. Yet there is a way to distinguish the difference between them other than the fact they have different names. And I'm not sure what other difference you can come up with between a list and a tree other than linearity and the lack thereof; they are built from the same basic objects (esp. considering a doubly-linked linear list and a binary tree); only the way they are assembled differs. (And a tree is not the only non-linear data structure; a circular list is another example that is perhaps closer to a linear list.) I'm going to hope that your inability to tell the difference between a list and a tree is temporary, based on your thread in GD, rather than go into a big long discussion about it here.

Popular pages Recent additions