Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [linked-list]

The tag has no usage guidance.

-3
votes
0answers
33 views

Linked List update priority

So i have created a linkedlist from scratch which inserts and sorts via priority. The last method i need to add is an update priority method. I have a findNodeByID method which finds a node based on ...
0
votes
1answer
61 views

How to safely walk a list to remove an element as well as associated elements safely

I have a single linked list of elements. Each element has a unique ID (positive integer) and a type. Each element may have a "sister" element, associated by its ID, that may also be in the list. The ...
0
votes
0answers
73 views

How to structure a bitwise trie to do a range query

I am wondering about how to perform a range query on a bitwise trie. So say I have a trie like this. ▲ Black (any shape) is 0. △ White (any shape) is 1. ■ Black square means there is no value ...
1
vote
1answer
48 views

Linked-list iteration patterns

If you have a linked-list, where the items are not necessarily close to each other in memory, wondering if it is (in general) better/worse/no difference to do the following. Say you want to iterate ...
-1
votes
1answer
82 views

Inserting at head for a recursively defined linked list

This article states However, this design does run into problems with some of the methods of the MutableSequence ABC. Most notably, insert and __ delitem __ can't operate on position 0, because ...
3
votes
4answers
898 views

Designing an efficient implementation of a random access queue based on a linkedlist

I'm currently working through Robert Sedgewicks "Algorithms in java" (3rd edition, german) on my own and am currently at one of the more complicated questions there. I think I may have the starting ...
3
votes
3answers
4k views

Why do we need stacks and queues?

I don't see the reason to have classes for stacks, queues and deques if we have the data structure linked list, since a linked list can act as both a stack and a queue (and always has the functions of ...
-1
votes
3answers
289 views

Mental model for working with linked list [closed]

I have been doing some practice problems on LinkedList but more than half of my time is spent on managing null pointer issue in my code, provided I have to keep track of current, previous and runners ...
1
vote
2answers
352 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
495 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 "...
3
votes
1answer
2k 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
182 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 ...
11
votes
3answers
5k 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 up a ...
2
votes
1answer
148 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
573 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 enough ...
0
votes
2answers
25k 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 ...
26
votes
7answers
5k 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 ...
2
votes
1answer
202 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 ...
6
votes
1answer
774 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 ...
2
votes
1answer
1k 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
522 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 ...
5
votes
3answers
618 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; ...
1
vote
1answer
290 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.
1
vote
2answers
1k 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 ...
2
votes
2answers
4k 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 ...
3
votes
1answer
436 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 ...
4
votes
6answers
3k 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
4answers
1k 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 ...
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
180 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
1k 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 ...
3
votes
3answers
5k 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 ...
5
votes
4answers
2k 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 ...
21
votes
5answers
3k 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 ...
17
votes
4answers
22k 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 ...
0
votes
2answers
945 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. ...