The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
2answers
193 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?
0
votes
1answer
60 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 "...
2
votes
1answer
213 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 ...
3
votes
3answers
92 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 ...
4
votes
3answers
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; ...
15
votes
4answers
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 ...
3
votes
2answers
179 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 ...
2
votes
1answer
95 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 ...
4
votes
1answer
422 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 ...
0
votes
2answers
2k 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 ...
24
votes
7answers
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 ...
0
votes
0answers
197 views

Finding meeting point of Slow and Fast pointers in Linked List Loop

I am aware that the solution for finding a loop using Hare-Tortoise approach works. I have a working code that is able to detect loops in a Linked List. My question is on how to find the meeting point ...
3
votes
1answer
383 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 ...
2
votes
1answer
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 ...
1
vote
3answers
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 ...
6
votes
1answer
220 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 ...
1
vote
1answer
377 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 ...
-2
votes
3answers
158 views

Is LinkedList an Abstract Data Structure? [duplicate]

This quote is from the book HeadFirst C: A linked list is an example of an abstract data structure. It’s called an abstract data structure because a linked list is general: it can be used to ...
1
vote
1answer
224 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.
0
votes
2answers
595 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 ...
1
vote
2answers
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 ...
0
votes
4answers
663 views

Linked list clarification

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 ...
3
votes
6answers
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 ...
0
votes
2answers
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. ...
1
vote
2answers
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 ...
1
vote
2answers
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 ...
4
votes
1answer
504 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 ...
5
votes
4answers
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 ...