Skip to main content

Questions tagged [linked-list]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
175 views

Are self-written queues and linked lists really worth it (better than built-in arrays)?

Let's say I need a queue for my project and the language I use does not have a built-in queue structure. So I decided to implement one myself. So I create an object with elements positions as the ...
forty5's user avatar
  • 39
2 votes
1 answer
1k views

How to properly delete nodes in a linked list?

I'm doing this homework exercise with simple linked lists in C with nodes having the following structure: typedef struct lista { int num; struct lista * next; } nodo; So the exercise asks us ...
4d4143's user avatar
  • 33
2 votes
1 answer
196 views

How to store a branching linked list in a database

I am trying to model an HVAC system for simulation purposes, which will consist of a series of components linked together by airflow and electrical flow paths. I'm trying to figure out how to best ...
Marshall Tigerus's user avatar
1 vote
1 answer
88 views

Converting binary tree into doubly linked circular list

I am a beginner in computer science and have been asked to write a program to convert a binary tree into a circular linked list (order of the nodes in list are in inorder traversal of the tree). I ...
bobthebuilder's user avatar
0 votes
1 answer
336 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 ...
Droopycom's user avatar
  • 103
1 vote
2 answers
127 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 ...
Lance's user avatar
  • 2,615
-1 votes
1 answer
120 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 ...
Trent Di's user avatar
4 votes
4 answers
4k 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 ...
Philipp Doerner's user avatar
5 votes
3 answers
9k 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 ...
NightSkyCode's user avatar
-1 votes
3 answers
413 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 ...
CodeYogi's user avatar
  • 2,176
1 vote
2 answers
996 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?
Daphne Preston-Kendal's user avatar
0 votes
1 answer
1k 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 "...
Alex Zywicki's user avatar
6 votes
1 answer
7k 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 ...
YoYo's user avatar
  • 586
3 votes
3 answers
344 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 ...
Omran Jamal's user avatar
11 votes
3 answers
22k 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 ...
Adam Zerner's user avatar
2 votes
1 answer
244 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 ...
Avineshwar's user avatar
4 votes
1 answer
580 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 ...
ApathyBear's user avatar
1 vote
2 answers
45k 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 ...
Spandan's user avatar
  • 21
30 votes
7 answers
7k 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 ...
Carcigenicate's user avatar
2 votes
1 answer
225 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 ...
Pieter Verschaffelt's user avatar
6 votes
1 answer
2k 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 ...
Goswin von Brederlow's user avatar
3 votes
1 answer
2k 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 ...
foamroll's user avatar
  • 135
-2 votes
3 answers
1k 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 ...
Koray Tugay's user avatar
  • 1,585
6 votes
3 answers
1k 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; ...
Michael Pankov's user avatar
1 vote
1 answer
633 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.
scerrecrow's user avatar
1 vote
2 answers
3k 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 ...
bazuzi's user avatar
  • 11
3 votes
2 answers
5k 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 ...
Goobley's user avatar
  • 191
3 votes
1 answer
665 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 ...
Shamster's user avatar
  • 141
6 votes
7 answers
5k 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 ...
Snappawapa's user avatar
0 votes
4 answers
2k 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 ...
sammy_123's user avatar
1 vote
2 answers
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 ...
Aseem Bansal's user avatar
  • 3,004
1 vote
2 answers
194 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 ...
John Cartwright's user avatar
4 votes
1 answer
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 ...
aaazalea's user avatar
  • 689
3 votes
3 answers
7k 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 ...
Chitrank Dixit's user avatar
5 votes
4 answers
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 ...
Geek's user avatar
  • 5,197
24 votes
5 answers
5k 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 ...
Kos's user avatar
  • 1,434
18 votes
4 answers
23k 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 ...
user avatar
0 votes
2 answers
1k 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. ...
Vinoth Kumar C M's user avatar