There’s code in one reply that spells it out, but you might find it easier to start from the bottom up, by asking and answering tiny questions (this is the approach in The Little Lisper): What is the reverse of null (the empty list)? null. What is the reverse of a one element list? the … Read more
Some implementations pass a pointer to pointer parameter to allow changing the head pointer directly instead of returning the new one. Thus you could write: // note that there’s no return value: it’s not needed void push(struct node** head, int data) { struct node* newnode = malloc(sizeof(struct node)); newnode->data=data; newnode->next=*head; *head = newnode; // *head … Read more
Linked lists are preferable over arrays when: you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical) you don’t know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big you don’t need … Read more
You can make use of Floyd’s cycle-finding algorithm, also known as tortoise and hare algorithm. The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes. If the linked list has a loop they will definitely meet. Else … Read more
Any alternative? No, this is as simple as it gets, and there’s no fundamentally-different way of doing it. This algorithm is already O(n) time, and you can’t get any faster than that, as you must modify every node. It looks like your code is on the right track, but it’s not quite working in the … 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
In most cases, List<T> is more useful. LinkedList<T> will have less cost when adding/removing items in the middle of the list, whereas List<T> can only cheaply add/remove at the end of the list. LinkedList<T> is only at it’s most efficient if you are accessing sequential data (either forwards or backwards) – random access is relatively … Read more
Node *current = new Node; Node *previous = new Node; This code causes memory leaks – you are never deleting this memory. You can declare pointers without memory allocation: Node *current = nullptr; Node *previous = nullptr; delete will delete the memory of the pointer so you will actually delete Nodes. But using delete[] for … Read more
The C code is pretty simple, actually. Expanding one macro and pruning some irrelevant comments, the basic structure is in listobject.h, which defines a list as: typedef struct { PyObject_HEAD Py_ssize_t ob_size; /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */ PyObject **ob_item; /* ob_item contains space for ‘allocated’ elements. The number … Read more
When to use LinkedList over ArrayList in Java?