Array Based Implementation of a Vector

Question

Homework Assistance

Describe an array based implementation of a vector such that inserting and removing at beginning and end of the vector can be done in constant time. Argue convincingly.

Obviously this is impossible with a straight-up array. If you remove from the front, there will be a hole that needs to be filled in order to maintain the vector property. Of course, if we grab the next element over, we will need to do this n times, so the runtime will be linear, not constant.

Another way would be to grab the last element and stick it in the front, but what good is a data structure that scrambles your data?

What I have done so far is to create an array. The odd number indices are behind some point in the array (preferably the middle for size purposes, but it can be anywhere), then the even number indices are before that point. That takes up a whole bunch of memory and has lots of open slots if that special point is not the centre point. Worst case being 2n. However, it acts like there are no holes because it will always fill the next element out.

Insertion:

private int front = 0;
private int back = 0;
public void insertAtFront(int element)
{
    (front+1));
        dataArray[2*(front + 1) + 1] =  element;
        front++;
}

public void insertAtBack(int element)
{
    dataArray[2*(back+1)] = element;
    back++;
}

For removal, just decrement the front or the back. Then when accessing the array, only allow the values between front and back to be shown.

First, does this meet the requirements of a vector? Second, when removing, I am having some major issues figuring out how to get past that special centre point. Say you want to remove the entire array from the front, when you added everything from the back.

Thank you for any assistance.

Tyler Durden · Accepted Answer · 2013-06-13 16:13:38Z

1

The secret is to use two arrays. The end of the first array is the "front". The end of the second array is the "back".

answered Jun 13, 2013 at 16:13

Tyler Durden

11.6k11 gold badges76 silver badges137 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sebastian Redl · Accepted Answer · 2013-06-13 16:09:46Z

0

I don't understand what you're trying to do with even and odd indices. But having a start index and an end index is basically the way to go - leave space empty at the front so that you can add elements there, and increment the start index again if you remove an element.

answered Jun 13, 2013 at 16:09

Sebastian Redl

73.9k8 gold badges137 silver badges177 bronze badges

Comments

Andrew · Accepted Answer · 2016-04-17 13:37:18Z

0

Another option is to use a circular array to allow you to add/remove both at the front and at the end efficiently.

There are other variations that could be applied: can you also find an implementation such that inserting/removing at the start, the end and (exactly) in the middle is efficient and has O(1) time?

answered Apr 17, 2016 at 13:37

Andrew

7698 silver badges24 bronze badges

Collectives™ on Stack Overflow

Array Based Implementation of a Vector

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related