Stack Exchange Network

Stack Exchange network consists of 175 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-lists]

The tag has no usage guidance.

2
votes
1answer
173 views

The origin of list data structure

Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?
0
votes
1answer
47 views

Linked List with Merge Sort

Is Merge Sort best sorting technique to sort linked list?and which sorting technique is worst in linked list? Merge sort uses divide and conquer method. How it can be sort a linked list efficiently?
6
votes
2answers
968 views

What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?

I’m trying to understand the time complexity of a queue implemented with a linked list data structure. My book says that we can the implement a queue in O(1) time by: enqueueing at the back ...
2
votes
1answer
35 views

Sorting elements of linked list

I've been looking over sorting algorithms for linked list and here's what I came up with. As we know, for element access arrays will work better than linked list. Also, there is the benefit of ...
1
vote
1answer
29 views

Binary trees and preallocated nodes

I want to design a binary tree with preallocated nodes, in order to avoid calling malloc/free every time I want to insert/delete a node. The problem is I don't know ahead of time how many nodes the ...
1
vote
1answer
20 views

A question about linked list

I would like to check the answer of this exercise: A circular doubled linked list with N elements has pointers that cost k bytes each of space in memory. How many bytes do the pointers of this list ...
0
votes
1answer
162 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...
1
vote
0answers
36 views

Terminology Questions: Data-structure consisting of lists without repetitions

I've google around and have been unsuccessful in finding a name for a data-structure consisting of a list whose elements are unique. I've seen "unique sorted lists", but I'm looking into the more ...
0
votes
1answer
38 views

time complexity of erasing repeated entries

This problem involves the time complexity of erasing entries that occur more than once in a list. I think it might be $n \log n$. Problem The input is a finite set $S$ and a finite list $T$ ...
3
votes
1answer
47 views

Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)?

I am struggling to understand why linked lists seem to be accepted to have better big-O performance than arrays for in-middle insertion/deletion. The performance differences between lists and arrays ...
0
votes
1answer
39 views

Linked List fundamental concepts [closed]

I am trying to understand the basics of Linked List. The definition of my LinkedList class is as follows: ...
1
vote
2answers
75 views

What is the complexity of finding the predecessor of a node in a doubly linked list?

This is a question from Cormen 3rd edition(exercise 10.1). I am of the opinion that the complexity should be O(1), as we just have to look into the next pointer of the current node. But the answers ...
2
votes
1answer
90 views

Linked List in Maximal Scoring Subsequences Algorithm

For a project, I'm implementing the All Maximal Scoring Subsequences algorithm. In the analysis portion of the paper, it describes an optimization that makes the algorithm run in linear time. Namely, ...
0
votes
1answer
849 views

How to find middle element of doubly linked list using head and tail?

Is there a way possible to find the middle element of a doubly linked list using head and tail. I tried traversing to the next element from the starting node and the previous element from the end node ...
-2
votes
1answer
44 views

Learning to prove correctness of simple linked-list algorithms

I understand how to use linked lists, and build algorithm using them. But I don't understand how can we prove their correctness, even of simplest algorithm. I haven't even found a good tutorial ...
-1
votes
3answers
753 views

Finding the nth to last node in a linked list

I have a linked list with n elements and my goal is to find the 'nth to last element' in the list. I would like to present my approach. Please provide your opinions on whether it is optimal or how may ...
0
votes
3answers
84 views

What is the only condition that would cause the Insert operation of a dynamic data structure to return a “data structure full” error?

I want to know where can I find some resources on this question, because, after researching for a day and half, I couldn't find information specific to my question. Can anyone help me answer my ...
0
votes
1answer
160 views

Finding an element in a infinite unsorted doubly linked list

Is there any way to find an element in an unsorted doubly linked list given an element and pointer from which we can navigate? (we can't use head/tail pointers since the list is infinite)
0
votes
4answers
748 views

Finding the $k$th largest element in an unsorted array

What is the complexity of finding the k'th largest element in an unsorted linked list? If we sort the list, I think that the complexity is O(nlogn + k)=O(nlogn) since k < n. Is there a way of ...
0
votes
2answers
51 views

Is linked list a preferable underlying basic DS for a collection mutable through an iterator

I need to implement a collection DS that exposes an iterator which can be used to iterate an underlying collection and possibly remove the current item. I can use either a vector (dynamic array) or a ...
3
votes
5answers
276 views

What precisely/concisely is the “head” of a singly linked list? I ask bc of ambiguity online

So I have a pic which I think illustrates my confusion: the read surrounds what I wonder is the head? Does head refer to a node with both a data and next, or only a node with next? In other words, ...
1
vote
2answers
214 views

Linked lists in practice

I have some questions about the ideas proposed in this video. The speaker shows an array that holds values and pointers, and he also shows a separate "free" linked list, that is updated whenever an ...
1
vote
2answers
1k views

What's the advantage of two pointers linked list implementation of Queue versus one pointer circular list

Princeton Algorithms course shows the implementation of Queue using linked list and two pointers - head and tail. I've ...
0
votes
1answer
290 views

What is the type of linked list where order doesn't matter

I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about linked listed implementation: Insertion into a singly-linked list is a nice exercise in pointer ...
0
votes
1answer
3k views

Insertion and deletion complexities for a linked list and array

I have the following table that compares different operation complexities for a linked list and array: ...
0
votes
1answer
233 views

What is `wasted space` parameter and why is it O(n) for a linked list

I'm reading a book on data structures and there is a comparison between linked list, array and dynamic array. The parameter name is wasted space. Here are the values: \begin{array}{cc} \text{...
0
votes
1answer
86 views

Given an algorithm, do worst case time complexity “class” vary with array and linked list?

My intuition says that I can make a sorting algorithm(may be a strange, not an useful), such that with array it have different worst case time complexity class and linked list(assuming time complexity ...
1
vote
2answers
658 views

Correct way to implement linked list

I'm doing this challenge on Hacker Rank that wants me to implement a linked list. It seems to want me to find the last-added instance of node and change its head to link to my new instance of node. ...
2
votes
2answers
409 views

Why do we use multiple data structures? [duplicate]

I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees. Both runs in worst case O(n) in the same operations, so why don't we use only ...
3
votes
1answer
617 views

Recursive definition of Matrix

Like Linked-list for Array, is there a recursive counter-part for Matrix? Is there a persistent data structure which can be used in place of Matrix in pure functional language like Haskell?
12
votes
7answers
12k views

How to find middle element of linked list in one pass?

One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.
1
vote
1answer
177 views

Using B-method, and formal methods in general, to model and verify a reverse linked list

I am trying to do some formal modeling of a linked list, however instead of referencing the next block, each block needs to reference the previous block instead. Is there already any formal methods ...
3
votes
0answers
240 views

Generalization of XOR Linked Lists

Are there any results generalizing XOR Linked Lists to other types of data structures? For example, just like an XOR Linked List requires two pointers and can iterate a 1 dimensional list, I can ...
4
votes
1answer
423 views

Best data structure for storing an ordered list, where each item is located on a separate server?

I need a structure that resembles an RSS feed of items, but each item is on a different network machine. Users cannot insert in the middle of the feed but only at its head. Deletions are possible. ...
2
votes
2answers
304 views

Why don't nodes carry as many pointers as possible in a skip list?

From this main picture explaining how skip lists work from Wikipedia, we see that some nodes carry different amounts of pointers to other parts of the list: Wouldn't it make more sense to have every ...
1
vote
3answers
180 views

Usefulness of a linked list with a cycle

Is a singly-linked list that contains a cycle considered a corrupted data structure or is there some practical use for it? (You could argue that a car without its front shield is not corrupted, if ...
2
votes
2answers
107 views

What is the trick used in skip lists to minimize $k + \frac{n}{k}$?

I was reviewing skip lists and the first step is to have two lists, the bottom one ($L_0$) of length n and the top one ($L_1$) of size k. Usually one traverses the "express line" (i.e. the top lane ...
3
votes
2answers
2k views

What is the average time complexity, for a single linked list, for performing an insert?

I thought this would be a very simple O(n) b.c. you can do the insert any where with in the list. The longer the list, the longer it will take on average to do the ...
-3
votes
2answers
241 views

If the list lengths are m and n, why does the merge take O(m+n) operations?

If I have two sorted lists. list A => 1 -> 2 -> 4 -> 11 -> 31 list B => 2 -> 31 -> 54 Now what should be the order of (sorted) merge and ...
6
votes
4answers
372 views

Order-preserving update of a sublist of a list of mutable objects in sublinear time

Description Say I have a source list like: ["a","b","c","d"] and want to run a capitalization filter so if I change, "b" to <...
7
votes
2answers
719 views

Is a stack machine with a forward read iterator Turing complete?

It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful ...
1
vote
2answers
611 views

Why the pointer in linked list is of structure type? [closed]

Since any node points to a memory location is there any specific need in using it's pointer as structure type.Why couldn't we use integer as the pointer type in linked list rather than structure?
1
vote
2answers
1k views

Time complexity for searching $k-th$ element from starting and ending of a linked list

What are the time complexities of finding $8th$ element from beginning and $8th$ element from end in a singly linked list? Let $n$ be the number of nodes in linked list, you may assume that $n > 8$....
2
votes
1answer
3k views

How is the directory implementation done using a linear list?

I am reading Operating System Concepts by Silberchatz, Galvin, Gagne and they write that a directory can be implemented using a linear list. [pg 470, 8th ed] However, I visualize directories as a ...
1
vote
0answers
105 views

Terminology for a partially unlinked doubly linked list?

Let's say you have a standard doubly link list implementation: struct List { int Number; struct List *blink; struct List *flink; }; and that you have ...
1
vote
2answers
23 views

Order of storage of pointers for a linked list of length n

I have a linked list in which I have kept the elements in order (increasing/decreasing). I want to be able to perform a binary search on this linked list. For this I am keeping pointers to the middle ...
-2
votes
2answers
2k views

Sort doubly linked list efficiently

How efficiently can a doubly linked list be sorted? The minimum I could get is $O(n^2)$. Can anyone suggest something better?
1
vote
1answer
206 views

Does this algorithm on a circular linked list ever terminate?

Suppose we have a circular linked list that has nodes $1$ to $n$. L is a pointer that points to node 1 (with label $1$). Note <...
6
votes
2answers
505 views

Using singly linked list instead of a doubly linked list?

Are there advantages of implementing a singly instead of a doubly linked list other than space?
-1
votes
1answer
89 views

Linked list implementation problem [closed]

Note its not a homework question, just practice Hi i have always seen linked list implementation in java using the following piece of code ...