Linked lists, arrays and queues

Linked lists, arrays and queues

1. Linked lists

   • The only disadvantage of the doubly linked list as compared to the singly linked list is the additional space used, because the doubly linked list requires two pointers per node

2. Stacks

   • The stack is a list-like structure in which elements may be inserted or removed from only one end
     • Stacks are less flexible than lists, but it is also more efficient and easy to implement
   • Array-Based Stacks
     • The array-based stack implementation is essentially a simplified version of the array-based list
       • The more important design decision to be made is which end of the array should represent the top of the stack
   • Linked Stacks
     • linked stacks are analogous to linked lists
       • Elements are inserted and removed only from the head of the list, and a header node is not used
     • from a time efficiency perspective, neither array-based stacks or linked stacks has a significant advantage

3. Queues

   • Queue is a list-like structure that provides restricted access to its elements. Queue elements may only be inserted at the back (enqueue) and removed from the front (dequeue)
     • It's a FIFO list: First in, First out
   • Array-Based Queues
     • The array-based queue is somewhat tricky to implement effectively, and a simple conversion of the array-based list implementation is not efficient
     • The more efficient implementation can be obtained by relaxing the requirement that all elements of the queue must be in the first n positions of the array
       • This way, both the enqueue and the dequeue operations can be performed in Θ(1) time because no other elements in the queue need be moved

Images and files in the map