Compare the dynamic array and linked list implementation
There are two typical ways to implement a double-ended queue, using dynamic arrays and using linked lists . In general, it may seem as though using a linked list is a no-brainer because of the increased speed in many of the essential double-ended queue operations. However, there is one specific area where using a dynamic array is useful.
Which of the following operations will be significantly easier if you implement a double-ended queue using a dynamic array as opposed to a linked list?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Linked lists are very good data structures to use if you're planning on making multiple edits. All that is required is moving a few pointers around to accomplish insertions and deletions. Arrays, on the other hand, require you to move all of the elements on one side of the deletion/insertion to accomodate the operation. Appending is very easy in both structures. The dynamic array keeps track of the length of the array, so it can immediately go to the end and simply add the element. The linked list can also know where the end is (when using a doubly linked list).
The main benefit to using a dynamic array in any scenario is randomized access and indexing. To find an element in the middle of a linked list, you need to traverse the entire structure until you find it. Arrays are nice because you can immediately index to an element using a number between 0 and the length of the list. This is done in constant time.