# Tagged Questions

The tag has no usage guidance.

3k views

### Is there any practical way for a linked node structure to be immutable?

I decided to write a singly-linked list, and had the plan going in to make the internal linked node structure immutable. I ran into a snag though. Say I have the following linked nodes (from previous ...
19k views

### What are concrete rules for using a linked list instead of an array?

A linked list can be used when you want cheap insertion and deletion of elements and when it doesn't matter that the elements aren't next to each other in memory. This is very abstract and I would ...
1k views

### Why are cons lists associated with functional programming?

I have noticed that most functional languages employ a singly-linked list (a "cons" list) as their most fundamental list types. Examples include Common Lisp, Haskell and F#. This is different to ...
221 views

### How to write a doubly linked list for multi-core use without global lock?

I'm trying to write a cyclic doubly linked list where the nodes or even the link pointers are locked individualy. Or a lock-free or even wait-free (I think that's not possible) implementation. The ...
1k views

### Understanding comparison using Big O notation

I was going through this heavily discussed and highly voted question on SO and stumbled across one comment that got 5 upvotes. So I assume this was a great comment.But it got my head spinning at the ...
424 views

### Why does `length - 2` recursively give you the center of a linked list?

I am reading through an Algorithms book and am working through a recursive solution to the following question: Implement a function to check if a linked list is a palindrome This is an easy ...
516 views

### How does a priority_queue maintain a heap on a deque efficiently?

In the C++ STL, priority_queue (heap) can be used with any underlying container, such as a deque. How does the implementation stay O(log n) if deques don't swap an item in index a with index b in ...
146 views

### Is storing data directly in a list node better than storing a pointer to data?

Suppose we have two different doubly-linked list structures: One has content of the node embedded directly in the node: struct Content { // some stuff }; struct Node { struct Node *next; ...
2k views

### How did programmers implement Linked list ideas before the object oriented paradigm?

Linked lists, as far as I have seen, are largely implemented using object-oriented ideas. (having an object that holds some information and the address of the next link). How were Linked-lists ...
94 views

### Is it odd if Nodes in a LinkedList held references to the List object?

Its like, I want to call .moveToBefore(Node) on a Node object and have the node relocate to before the node passed in. The problem arises if the node passed in is the head node. The List object will ...
189 views

### Should Linked Lists always have a tail pointer?

My understanding... Advantages: Inserting at the end is O(1) instead of O(N). If the list is a Doubly Linked List, then removing from the end is also O(1) instead of O(N). Disadvantage: Takes ...
386 views

### How can I rewrite this linked-list manipulation as tail-recursive?

Given a liked list, I'd like to swap every pair of nodes as follows: input: a-b-c-d-e-f-g output: b-a-d-c-f-e-g If there's an odd number of nodes then the last node is tacked on as-is. This should ...
215 views

### LinkedList - why no direct .next() on elements?

I never understood this: why is it that I can't seem to find a core collections api somewhere that Allows me to retrieve elements that have a direct .next() or .previous() method on them without all ...
187 views

### Θ(1) algorithm that removes one element from a linkedlist

I have to find a Θ(1) solution to the following problem: You're given a singly linked list and a reference to one of the elements in the list. You can be certain that this is not the last element in ...
96 views

### Bus bunching simulation code [closed]

I'm having a peculiar issue to solve. What I am supposed to implement is a bus transit simulation in which there are passengers coming at some random generated time intervals and are added into a ...
225 views

### Is a linked list an actual data structure?

I hear conflicting sides from this topic. I was under the impression that a linked list was a way to implement a data structure (stack, queue), not actually a data structure.
200 views

### Do any languages other than Haskell implement strings as linked lists of characters?

Haskell’s String type is an alias for [Char] (i.e. a linked list of Chars). Does any other language use an implementation of strings like this?
1k views

### Better design for a generic doubly linked list around which I plan to make different wrappers?

I am currently writing a C code for a doubly linked list(dll) around which I want to write wrapers for implementing stack, queues etc. instead of writing separate codes for all of them. I'll be ...
169 views

### Building a sequential list in languages with cons/linked lists

In languages where cons lists are a major datatype, it is very easy to create a list from last to first by prepending items. When doing processing from some input file, however, one is most likely to ...
391 views

### What are the time and space complexities of this recursive method that reverses a singly linked list?

What are the Time and Space complexities of this Java method that reverses a singly linked list (of length n)? I'm more interested in knowing the reasoning behind the space complexity. Let me know if ...
2k views

### Does the Head(start) pointer of Doubly Linked list points previously to the tail(last) node

I have one question in my mind that in case of circular doubly linked list the head pointer of the doubly linked list also logically point to the next pointer of the tail node of the linked list and ...
2k views

### 2D linked list vs. multidimensional array/vector

I hope that programmers is the correct stack exchange for this, as it is quite a concept based question. I'm working on a data structure in C++ that is a represents data in 3D space. The x-y plane is ...
599 views

### C Linked List Implementation Pointer vs. Pointer-to-Pointer Consistency

To get some practice in C, I'm writing some basic functions for operating on a linked list of ints. I started out with functions that accepted as a "list" a pointer to the head node. Now, I find ...
668 views

This is a pretty simple question but I'm new to java. The linked list found in java.util.LinkedList. I saw elsewhere that Java does not use pointers... When I create a new list and add new elements ...
3k views

### C: How does struct node * next work? [closed]

In C, for creating linked list we write: struct Node{ int data; struct Node* next; }; So, my understanding is "struct Node* next" is a pointer variable of "Node" datatype. But how does it point to ...
62 views

### How to traverse “linked list” like structure with parallel nodes

I am working on a signal processing project that allows for parallel processing on data streams as well as inputs and outputs to and from multiple endpoints. The signal chain is broken down into "...
883 views

### Question regarding LinkedList in Java

When I was reading a book for SCJP, I came across the following paragraph. A LinkedList is ordered by index position, like ArrayList, except that the elements are doubly-linked to one another. ...