Arrays insertion/deletion linear?

This is a discussion on Arrays insertion/deletion linear? within the C++ Programming forums, part of the General Programming Boards category; So, I understand why arrays have fast random access(Searching) or constant time access for searching, because you have an index ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    30

    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. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    30
    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. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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. #5
    Registered User
    Join Date
    Sep 2008
    Posts
    30
    Awesome, Thanks for the help. Glad I got that straightened out. Its was really bothering me
    Last edited by jakemott; 07-11-2009 at 03:03 PM.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by jakemott View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    It's named after the abstract data type linear list, which is what C++ calls a sequence.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by CornedBee View Post
    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. #9
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    Quote Originally Posted by tabstop View Post
    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"
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by brewbuck View Post
    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. #11
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    Quote Originally Posted by tabstop View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by brewbuck View Post
    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. #13
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    Quote Originally Posted by tabstop View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #14
    Registered User
    Join Date
    Sep 2008
    Posts
    30
    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.
    Last edited by jakemott; 07-11-2009 at 11:47 PM.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by brewbuck View Post
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Need Help With 3 Parallel Arrays Selction Sort
    By slickwilly440 in forum C++ Programming
    Replies: 4
    Last Post: 11-19-2005, 09:47 PM
  3. Crazy memory problem with arrays
    By fusikon in forum C++ Programming
    Replies: 9
    Last Post: 01-15-2003, 08:24 PM
  4. Linear search and 2d arrays?
    By sven in forum C Programming
    Replies: 0
    Last Post: 02-08-2002, 04:26 AM
  5. arrays, linear linked lists and binary trees
    By jasingle in forum C++ Programming
    Replies: 2
    Last Post: 11-12-2001, 10:12 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21