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
You can detect it by simply running two pointers through the list, this process is known as the tortoise and hare algorithm after the fable of the same name: First off, check if the list is empty (head is null). If so, no cycle exists, so stop now. Otherwise, start the first pointer tortoise on … 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
Remember that big-O complexity describes asymptotic behaviour and may not reflect actual implementation speed. It describes how the cost of each operation grows with the size of the list, not the speed of each operation. For example, the following implementation of add is O(1) but is not fast: public class MyList extends LinkedList { public … 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
You did a great job with your level of commenting, style, and the program layout. Some of the best I’ve seen on SO. Overall, a good effort. However, there were bugs. I’ve produced an annotated version of your code and a refactored one. See below. There were a number of bugs throughout the code, not … 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
Supposedly we have a general class of Node and class LinkedList based on the above allowing the user to add, remove etc. Now, how would we ensure immutability? You ensure immutability by making every field of the object readonly, and ensuring that every object referred to by one of those readonly fields is also an … 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
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