Thread: 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.

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.)

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.

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.

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".

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.

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.

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.