LinkedList might allocate fewer entries, but those entries are astronomically more expensive than they’d be for ArrayList — enough that even the worst-case ArrayList is cheaper as far as memory is concerned. (FYI, I think you’ve got it wrong; ArrayList grows by 1.5x when it’s full, not 2x.) See e.g. https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt : LinkedList consumes 24 … Read more
It is certainly not possible with a plain singly-linked list. Sketch proof: to examine the last node of a singly-linked list, we must perform n-1 operations of following a “next” pointer [proof by induction on the fact that there is only one reference to the k+1th node, and it is in the kth node, and … Read more
Easier one: Go through your linked list, save the previous and the next node and just let the current node point at the previous one: void LinkedList::reversedLinkedList() { if(head == NULL) return; Node *prev = NULL, *current = NULL, *next = NULL; current = head; while(current != NULL){ next = current->next; current->next = prev; prev … Read more
Draw out a stack trace… Intial – {1,2,3,4} Head – 1 Rest = 2,3,4 Recurse(2,3,4) Head = 2 Rest = 3,4 Recurse(3,4) Head = 3 Rest = 4 Recurse (4) Head = 4 Rest = null //Base Case Reached!! Unwind. So now we pick up Recurse(3,4) Head = 3 Rest = 4 // Return picks … Read more
It’s definitely more a quiz rather than a real problem. However, if we are allowed to make some assumption, it can be solved in O(1) time. To do it, the strictures the list points to must be copyable. The algorithm is as the following: We have a list looking like: … -> Node(i-1) -> Node(i) … Read more
No, a bucket is each element in the array you are referring to. In earlier Java versions, each bucket contained a linked list of Map entries. In new Java versions, each bucket contains either a tree structure of entries or a linked list of entries. From the implementation notes in Java 8: /* * Implementation … Read more
Inserting nodes. First… The code! #include <iostream> struct listItem { //creating a node int data; struct listItem *next; }; //function to insert items void Insert(listItem *&head, int item) { listItem **curr = &head; // start at head while (*curr != NULL // while there is a node && (*curr)->data <= item ) // and the … Read more
Some brands of database (e.g. Oracle, Microsoft SQL Server) support extra SQL syntax to run “recursive queries” but MySQL does not support any such solution. The problem you are describing is the same as representing a tree structure in a SQL database. You just have a long, skinny tree. There are several solutions for storing … Read more
Linked structures are possibly the worst structure to iterate with a cache miss on each element. On top of it they consume way more memory. If you need add/remove of the both ends, ArrayDeque is significantly better than a linked list. Random access each element is also O(1) for a cyclic queue. The only better … Read more
For some needs, a deque may also be useful. You can add and remove items on both ends of a deque at O(1) cost. from collections import deque d = deque([1,2,3,4]) print d for x in d: print x print d.pop(), d