The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [circular-list]

A circular list may be implemented using a fixed-size array (a ring buffer) or a linked list.

Filter by
Sorted by
Tagged with
4
votes
1answer
3k views

C++ Circular buffer through Circular iterator

I saw some question on SO lately involving circular buffer, like a chain of descriptors for data transfer. All solutions involved lots of lines. I wanted an implementation with as few lines as ...
4
votes
3answers
518 views

Producer-Consumer with Peterson algorithm in java

Producer-consumer problem in Java with a circular buffer of N positions. There is a single thread representing the producer that will produce consecutive integer elements There is a dimensioned ...
9
votes
2answers
3k views

Circular Buffer C++ Implementation

I was asked this question in an interview, and didn't go through. I know, it needs some improvements, but probably I am missing something big? I would highly appreciate if someone can review it for me,...
9
votes
1answer
133 views

Rotate a given number of variables in-place

A very simple but useful algorithm: rotate the values of a given number of variables in-place to the left so that the first variable gets the value of the second, the second gets the value of the ...
7
votes
1answer
987 views

Implementation of fixed size queue using a ring (cyclic) buffer

I found myself in need of a fixed size queue and decided to implement one using a ring (cyclic) buffer. I have tried my best to match the API of std::queue with ...
0
votes
1answer
2k views

Deleting the head node of a circular linked list

Today I tackled this coding challenge: Given a circular linked list, implement a method to delete its head node. Return the list's new head node. I would appreciate any feedback. ...
4
votes
2answers
2k views

Circular buffer implementation using linked list

I'm a beginner with C. The below is the implementation of circular buffer using linked list. Please review my code and suggest any improvements to make it efficient or to improve in coding style. <...
4
votes
1answer
829 views

Circular doubly linked list with templates

I tried to write some code namely "Circular doubly linked list" and I would like to use templates to do this. This is the first time I use templates and throws some exceptions. I would like to know ...
2
votes
1answer
3k views

Implementing a queue using a circular buffer

I'm working on implementing a queue using a circular buffer problem. Any smarter ideas for better time complexity, any code bug or code style advice are highly appreciated. ...
9
votes
3answers
30k views

Circular Buffer C++11 Implementation

Here's the implementation of a common data structure I use at work, mainly for logging purposes. I tried to make it C++11-compliant, but even if this standard has been around for a few years, it is ...
3
votes
4answers
3k views

Circular array rotation Java

I have a solution to the HackerRank Circular Array Rotation challenge. It passes 7 test cases out of 15. The rest of them are getting timed out. I think it's because of the huge data set that has ...
4
votes
1answer
484 views

Circular doubly linked list in JavaScript

I've been studying data structures and have taken a stab at implementing a doubly LL in JavaScript. Please review and advise on any additional improvements and optimizations. I'm more interested in ...
0
votes
1answer
293 views

Shift an element in a circular container

I implemented a function to shift an element after another in a logical circular array. Shifting in this case simply means moving element at position i to in front ...
2
votes
1answer
74 views

Invert-range operation in a circular vector

I implemented a invert-range operation in a (logical) circular vector. A circular vector is a vector without a logical starting and ending object, or, equivalently, the successive element of the ...
1
vote
1answer
45 views

Delete the node at index i from its current position and insert it after node at index j

I was trying to create a function to delete the node at index i from its current position and insert it after node at index j ...
2
votes
0answers
496 views

Concurrent resizable ring buffer

I'm trying to find the fastest way to enqueue and dequeue items concurrently in Go. There are some restrictions: it needs to be unbounded Memory allocation should be low Multiple producers (Single ...
6
votes
2answers
1k views

Ring buffer in Ruby

I was just reading about ring buffer the other day and I was fascinated by how simple yet efficient it is. I've implemented a ring (circular) buffer in Ruby and I'm just wondering if there's anything ...
4
votes
1answer
113 views

Rotating list in python

This is a list class which allows users to "turn" the list while keeping track of the current position. For efficiency, the list is not actually rotated on each rotation, but instead an offset keeps ...
4
votes
3answers
3k views

Lock free MPMC Ring buffer implementation in C

I have written a lock free MPMC FIFO in C based on a ring buffer. It uses gcc's atomic built-ins to achieve thread safety. The queue is designed to return -1 if it's full on enqueue or empty on ...
6
votes
5answers
3k views

A buffer that holds and provides the latest n items

I have developed the following code to hold n latest items it has received, and when asked for provide these n latest items. The interface is: ...
5
votes
2answers
2k views

constant sized circular (ring) buffer

I've implemented constant sized circular buffer. It provides push and pop operations, along with modern emplace. It is also optimized for destruction of trivially destructible types. I didn't include ...
2
votes
3answers
19k views

Josephus Problem in Java

Problem The Josephus Problem is a famous mathematical puzzle that goes back to ancient times. There are many stories to go with the puzzle. One is that Josephus was one of a group of Jews who ...
7
votes
1answer
26k views

Left Shifting an array of ints

The problem I am referring to is here So basically it's about shifting an array of ints 1 position to the left and relocating the lost first int in the start of ...
2
votes
3answers
14k views

“Prev” / “Next” buttons for a circular list

I have an array of strings and on click of the "NEXT" button it displays the next array item in a <p> tag while on click of the "PREV" button it displays the ...
3
votes
1answer
2k views

Circular Queue using Linked List

I want to create a circular queue using a linked list. I also want to create many instances of that data structure (queue) without repeating the code. This is what I came up with: ...
10
votes
2answers
1k views

Circular Buffer in C - Follow Up

This is a follow up to this post I uploaded a few days back on my alternative account about a circular buffer in C. I'm confident that I fixed most of the warnings and even added an iterator. ...
3
votes
1answer
10k views

Insert in circular linked list

Please review my code. ...
18
votes
1answer
1k views

C and CUDA: circular buffer implementation

I have a programme which uses many circular buffers in an identical fashion on a CPU and GPU (C and C/C++ CUDA). I essentially require many queues, however, due to this being run on a GPU, I have ...
8
votes
3answers
363 views

Circular Buffer

For my current project I need a circular buffer, which is able to do the following things: Push something to it (to the head). Pop something from it (from the tail). I don't need the popped data. ...
11
votes
5answers
589 views

FiniteArrayQueue type with interface and unit tests

Doing some exercises on basic data structures, I learned about queues, and decided to roll my own to better understand how a basic queue can function. As the name indicates, this Queue is made from a ...
6
votes
1answer
157 views

Rate limiting function calls

I wanted to write a function that when applied to another would rate limit it, but permit all calls to eventually make it through. Comments and criticism welcome. ...
4
votes
3answers
583 views

Implementing CircularQueue using Linked List in C++

I'm currently doing a project, requiring me to implement a CircularQueue data structure in C++: ...
2
votes
3answers
137 views

ADT Stack with a doubly circular linked list

I have managed to implement an ADTStack with a circular doubly linked list. I would like to know whether there are things I could have done better or, I should ...
12
votes
5answers
16k views

One reader / one writer no-memory-allocation lock-free ring-buffer

I have two threads - one thread queues items another thread dequeues. dequeue is fast enough and so we can assume that queue is never contains more than 65536 items....
2
votes
1answer
577 views

Doubly circular linked list implementation

I made this C++ doubly circular linked list implementation and it seems to work right, handle everything well, and not have any errors. However, I've been working with it for a while and would like ...
2
votes
1answer
766 views

Circular array list in C

Now I have this circular array-based list in C. Circularity allows pushing/popping to the both ends of the list in constant amortized time. Inserting/removing at random locations runs in linear time, ...
7
votes
1answer
815 views

Stack using an array

I designed a simple drop-out stack a while back. Basically, I just want to get a few opinions on whether or not this is a good implementation and whether I am understanding the concept of a drop-out ...
4
votes
3answers
288 views

Finding the tallest and find the index number of the next taller guy in a circular queue

Input given is: Each test case contains two lines. The first line contains a single integer N (1 ≤ N ≤ 105), the number of persons playing the game. The second line contains N integers i(height) (1 ...
5
votes
1answer
4k views

Lock-free ringbuffer with multiple readers in C++11

Basic Info I needed a lock-free ringbuffer with multiple readers (but one writer). However, I did not want the writer to check all readers every time in order to prevent an overrun. Thus, I decided ...
3
votes
2answers
1k views

Ring buffer for audio processing (follow up)

This question is a follow up in regards to the comments suggested in a previous post regarding a Ringbuffer implementation in C++ for audio processing. Ring buffer ...
6
votes
2answers
2k views

Ring buffer for audio processing

Below is my source code for the implementation of a Ring/Circular buffer for use in audio processing. I have been using this implementation for several months now but I have some doubts about the ...
3
votes
2answers
630 views

Linear Probing in Python

About to get back into coding, so I implemented linear probing in Python. How did I do? Anything unnecessary? Am I using "global" right? I originally wanted to use an array with a fixed length, but ...
6
votes
2answers
13k views

Thread-safe message queue without mutex in C

I'm trying to write a message queue implementation so my threads can exchange data. To keep things simple, the queue is only responsible for sending pointers to memory. Only one thread may send ...
3
votes
1answer
3k views

Array slice type in Java

Edit See the next iteration at Array slice type in Java - follow-up. I have this "slice" type for managing array subranges. It is kind of the same thing as Pythons slice notation, yet I did not add ...
1
vote
0answers
126 views

Array slice type in Java - follow-up

See the previous iteration. I have essentially fixed most of the issues mentioned by maaartinus. However, I left the size field as it is. Namely, if the user wants ...
3
votes
0answers
136 views

Ring Buffer using templates/macros

I just wrote my first Nim module and was hoping someone with some experience with Nim or similar languages could take a look. In particular I was hoping someone could speak if the use of ...
1
vote
2answers
242 views

Is this circular linked list better than the fast & slow pointer method?

I have a faster way to find if a list is circular linked list, in contrast to the solution that Cracking the Coding Interview has offered: In the below algorithm, ...
3
votes
1answer
1k views

Bootstrap show many move one carousel modification

I've been steadily improving a show many move one carousel sample that I found a few weeks ago. I want to post my improvements for others to use but don't want to spread bad code. I'm not an expert in ...
8
votes
1answer
491 views

Ring datatype in Python

I wanted to write something that would be useful for the indices of a grid where if one walked off the edge of the grid they would re enter on the opposite side. This could in theory help with ...
3
votes
1answer
6k views

Efficient Ring Buffer (FIFO)

I need to implement a Ring Buffer/FIFO for data coming from a TCP socket. It must support the following operations: Append a the recv()'ed chunk of bytes. Allow me to peek at the beginning of the ...