# Tag Info

21

This is called a doubly linked list. List<T> is basically a wrapper around an array. The only operations where you can hope to be faster are insertions and deletions from the middle of the list. Using Marshal unless you absolutely have to is a bad idea, if not a plain crazy one. This code has memory leaks (how is that destructor meant to release all ...

16

Collection != enumerator The main problem I see here is that LinkedList<T> implements IEnumerator<T> instead of IEnumerable<T>. That's the wrong interface, which makes this class quite difficult to use: you now have to manually call MoveNext() and Current, instead of being able to use foreach. This also prevents you from using Linq methods,...

16

Next time you're in such a scenario, ask them to clarify what "academic" means. For me it means a solution that concentrates on the essence of data structure, not an implementation of a specific API. But we probably never know so let's not concentrate on that. Instead, let's look at the red flags... (I have ignored the comments as I do not understand the ...

14

Design Please use a namespace for your classes. Polluting the global namespace is bad practice. You implemented a singly linked list. With just a tiny bit more effort you could have implemented a doubly linked list which is arguably much easier to add all the functionality you would expect. You use head/tail with nullptr. This means your code is full of ...

13

size++ should be extracted from both branches and called only once there is no need to cache instance variables where local method variables should be used instead: newNode,oldNode,displayNode prefer while(currentNode != null) over while(true) and currentNode should start with firstNode and be chained inside the while-loop as currentNode = currentNode.next ...

12

Naming It's unconventional to name a type with all-uppercase - we normally reserve those names for preprocessor macros, to warn readers that they need treating with care. Avoid such names for ordinary identifiers. Avoid using identifiers that begin with an underscore - in many situations, those names are reserved for use by the implementation, which could ...

10

First some minor issues with naming, then a rewrite: prev could be previous, there is no need to skimp on characters. node_j and node_i are completely different things, yet their names suggest they are both "moving pointers". That is only true for node_j. May I suggest using current and insert instead? The use of while..else is pretty cool, but confused me ...

9

You've essentially built a doubly-linked list that also performs its own memory management. Regarding linked lists: This makes indexing is an $O(n)$ operation, compared to $O(1)$ for List<T>. Searching from the end for indexes beyond the center helps, but it does not fundamentally change this performance characteristic. Adding is an $O(1)$ ...

8

The space complexity of your solution is $O(n)$. What if I told you that given the constraints in the question, you could solve this problem in $O(1)$ space? Consider that you receive an already sorted list. This implies that all duplicates must be adjacent. This in turn means that for deduplicating these, you do not need to keep track of which values ...

8

I've made the Node class public so I can use it for a binary tree implementation later I don't think you can use this Node type as a node in a binary tree, because nodes in binary trees typically has references to other nodes like Parent, Left and Right. So IMO keep this Node class as a dedicated node type for this linked list: public class LinkedList<...

8

- float float constants need the suffix f: static const float EXPANSION_POINT = 1.0f; if not, you're assigning a double constant implicitly converted to float. - functions that accept 0 parameters Functions that accept 0 parameters should always be defined as type foo(void) type foo() means different things depending on the context. It is different ...

8

I can add that instead of DisplayLinklist() you should override toString() that returns a String representation of the linked list. then the caller can decide where and how to display this String.

7

All of your methods on Node are useless. Just use Node.val and Node.next like you already are. insert_after_key is likely to insert the data multiple times if there are multiple keys. Given how insert_before_key works differently you should test you code with unittests. Your code fails silently. I don't recommend this. You can remove the looping from all ...

7

Style POSIX reserves type names ending with _t. This means that in the future, standard c may create standardized types with the same name as string_list_node_t, and your code would not compile. See https://stackoverflow.com/a/12727104 for more details. A common alternative is to use upper camel-case for typedefs, e.g. StringListNode. There is a strong case ...

7

Use extension methods I find you did well by implementing the EverySecondElementIterator as a separate class. However, I also think it would be better to turn it into an extension of IEnumerable<T> and use MoveNext instead of the internal Node. Otherwise if someone suddenly comes up with the idea to skip every third element, you would need to modify ...

7

If we continue with the idea that this is a doubly linked list rather than a vector, I'd say your push_back and pop_back are a good start. Your Struct is also perfect for the groundwork of a doubly linked list. However, on that note, you're missing a few operations for this data structure to be considered a proper doubly linked list. A doubly linked list ...

7

What do I like? You use an initializer list in the constructor of Blinkedlist, and you are initializing all the primitive-type members in the correct order. You are using the more safe nullptr keyword instead of plain old NULL. You try to resemble the STL container interface that is well-known by C++ programmers. Mimicking the interface even extends to ...

7

You can have following changes: createNode size++ done outside of if..else.. In Node constructor if param next is always null then no need of this param. class and method name should be in camelcase as per java convention.

7

I'm not a big fan of your type-hinting comments. Let JavaScript be JavaScript. If you want typing, practice TypeScript instead. I find it counterintuitive that the ListNode constructor takes its next parameter before its val parameter. Putting val first is more natural (see my piDigits example below), and also allows next to be omitted for the last node ...

7

if (k > 0 && head != null) { ... return RotatedList; } return head; would be clearer (and more consistent with the other special case) as if (k <= 0 || head == null) { return head; } ... return RotatedList; (although really if k < 0 I think it should ...

7

With regard to the academic solution, perhaps they were referring to things like you would see in an assignment such as line lengths, appropriate naming and use of visibility modifiers, no compilation errors, etc. I feel your javadocs could have been better, equally there are @params that have no detail about the expected parameter such as in the add(E ...

7

Hi Jim Diroff II and welcome to CodeReview, Your code looks sane and I didn't spot any leaks. In printlist() why are you using a double pointer? This is only required if you intend to modify the pointer value, which you don't. Better use a normal pointer here: void printlist(NODE *head) { NODE *tracer = head; while (tracer != NULL) { ...

6

__getitem__, __setitem__, and __delitem__ should share index-validation and repair code. In __delitem__ you check the type of index as well as its algebraic sign (whether it's negative). In __getitem__ and __setitem__, you check only the algebraic sign; did you intend to not check the type of index in those two functions? If so, you should comment on why. If ...

6

My review is focused on linkedlist.c: Some functions don't check for null pointer (get_node_val, set_node_val). While it's documented, other functions do check for null pointer. The functions to append and prepend nodes require the caller to call the function to create a node. It might be a better idea to create the node in the function and to return the ...

6

Memory check Running the provided test program under Valgrind reveals quite a few problems: valgrind --leak-check=full ./221317 ==9150== Memcheck, a memory error detector ==9150== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==9150== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info ==9150== Command: ./221317 ==9150== ...

6

This isn't the really basic linked list. For the most basic way of doing linked lists, you would get rid of class linkedlist entirely, and have class Node be the entire implementation. You need both getters and setters for both item and next, and those four plus the constructor are really the only primitive operations there are. Every other list operation is ...

6

Performance You have implemented Floyd’s Cycle-Finding Algorithm which adheres to $0(1)$ storage space. An alternative exists Brent’s Cycle Detection Algorithm which uses the same storage space. Check out this review on Computer Science SE for a comparison. It appears in general, Brent's algorithm is faster. According to Brent's paper, the complexity ...

6

Nested types All “dependent” types are defined within the scope of LinkedList, which is good. To reference those types from within LinkedList you don't have to prefix the outer type. For example, public func index(before i: LinkedList<Element>.LinkedListIndex<Element>) -> LinkedList<Element>.LinkedListIndex<Element> can be ...

6

Using an uppercase name for a variable is a bad practise; should be rotatedList or preferably res for result or something similar. Separate your instantiations with semicolons: ListNode tail = head; ListNode rotatedList = null; ListNode kthnode = head; ListNode kthPrevNode = head; Your naming of head and tail ...

6

(Note: Martin York posted an answer when this answer is halfway done. The already written part will be left as is, but I try to avoid duplicating content after that. Make sure you read that answer as well!) General These are general suggestions: First of all, please write the declaration of a template class on two lines and use more spaces — ...

Only top voted, non community-wiki answers of a minimum length are eligible