Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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
29
votes
1answer
7k views

100 gunmen in a circle kill next person

I am very happy because I solved this problem with very little code: ...
19
votes
2answers
3k views

A Python wrap-around list

I want to gain experience creating data structures that look and feel like Python builtin types. As a first exercise, I've written a WraparoundList class meant to ...
18
votes
3answers
20k views

Index into array as if it is circular

The problem: Treat an array as if it is circular; out-of-bounds indices "wrap around" the array to become in-bounds. Current solution: ...
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 ...
17
votes
2answers
2k views

O(1) lock free container

This is a lock-free Container class. By Container I mean it will hold objects for iteration at a later time. To achieve \$O(1)\$ ...
15
votes
1answer
1k views

CircularListCursor - an efficient circular cursor on any list

I have decided to create my own CircularListCursor, because I wanted some abstraction and a ListIterator<E> couldn't give ...
13
votes
2answers
1k views

Circular FIFO Buffer

I was bored the other day and got to wondering how I would implement a circular FIFO buffer in Rust. My goal was to create an implementation I could use on a bare metal microcontroller. This means no ...
13
votes
2answers
1k views

Asynchronous Circular Buffer in C#

Preamble I want to be able to test methods which communicate over a simple exclusively asynchronous two-way stream-like interface which may underneath use any of a number of communication methods (e....
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....
12
votes
3answers
20k views

Circular RingBuffer

I am trying to get into C stuff, and I thought it would be a good idea to try and implement a circular buffer. I have defined my struct like this: ...
11
votes
5answers
590 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 ...
11
votes
3answers
9k views

Doubly-Linked Circular Linked List

I'm a C++ programmer learning Java in preparation for an OOP class this fall. That being said, Java is fairly new to me so I'd love to hear feedback on how to improve this code. A few notes: Code ...
10
votes
4answers
2k views

Advent of Code 2017, Day 1: Sum of digits matching the next digit (circular list)

I haven't used C++ for quite a while and wanted to practice a bit, so I decided to start simple and work through the Advent of Code 2017. This is my solution to Part 1 of the Day 1 exercise "Inverse ...
10
votes
4answers
5k views

Circular Bounded Queue using C#

As an exercise, I have implemented a circular bounded queue using arrays as the base data structure. I'd appreciate it if someone can review it for me. ...
10
votes
2answers
10k views

Circular Buffer Implementation

I'm implementing a "live analytics" feature and I need to always keep track of the last N items that were added to a collection so I figured I'd make a circular buffer since I couldn't find one. I ...
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. ...
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
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 ...
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 ...
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. ...
8
votes
2answers
5k views

Ring Buffer Implementation in C++14

A ring buffer or circular buffer is a fixed sized queue that advances head and tail pointers in a modulo manner rather than moving the data. Ring buffers are often used in embedded computer design. ...
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 ...
7
votes
2answers
1k views

Counting number of nodes between two nodes

This code counts the number of nodes between any given two nodes in a circular linked list. Any feedback is appreciated: ...
7
votes
2answers
266 views

Cyclic queue using an array

I tried to implement a cyclic Queue using an array, as a task from a coding interview. Please comment about style, as well as any edge cases I may have missed. ...
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 ...
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 ...
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 ...
7
votes
2answers
5k views

Circular buffer implementation for buffering TCP socket messages

I have written my own for practice and also some tweaks for my specific requirement. There is an insert which can copy a range (well array copy really) which I am hoping is more efficient than ...
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: ...
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 ...
6
votes
3answers
4k views

Elegant Circular Buffer

I would like to design an elegant yet efficient circular buffer of integers. I have designed a FIFO type circular buffer in C++(11)- starting with the class header (declaration) as follow: [...
6
votes
2answers
4k views

Queue implementation without using built-in data structures

In an effort to brush up my algorithms and data structure skills I have a done a queue implementation without using built in data structures, i.e. using only arrays. Any comments on this code ...
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 ...
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 ...
6
votes
1answer
1k views

Multiple-producer, single-consumer lock-free circular queue

I'm working on a firmware on a bare-metal ARM single core processor (Cortex M4), with no RTOS. I need to add a multiple-producer, single-consumer, lockless fixed-size circular (ring) buffer to the ...
6
votes
1answer
4k views

Multi threaded circular buffer

I've written a circular buffer with multithreaded write and single read ability: ...
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. ...
5
votes
5answers
21k views

Circular queue implementation

I've implemented a simple thread-safe circular queue. I'm looking for code review, optimizations and best practices. ...
5
votes
5answers
45k views

Shift elements left by n indices in a list

For the following question, the function • should mutate the original list • should NOT create any new lists • should NOT return anything Functions that do not create new lists are ...
5
votes
2answers
547 views

Circular linked list of integers

I'm looking for a review paying special attention as to whether the code can be optimized in the form of number of variables used, especially for the delete() ...
5
votes
4answers
2k views

Survivor programming challenge

I am working on a survivor problem: Complete Question Text: Take a second to imagine that you are in a room with 100 chairs arranged in a circle. These chairs are numbered sequentially from One ...
5
votes
2answers
1k views

Compare two lists to see if one is a rotation of the other

Going through a list of common interview question, this was the next one. Any suggestions on performance and improvement? What would be a better implementation of this? Also correct me if I'm wrong, ...
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 ...
5
votes
1answer
3k views

Single consumer and single producer lock-free circular buffer

I'm pretty new to multithreading. The code below is a simple implementation of a single consumer/single producer circular buffer that does not use any locking, that I wrote for fun. The question is,...
5
votes
3answers
845 views

Cyclic iterator in both directions

I am trying to make a cyclic iterator that works backwards and forwards. getNext() gets the next array item, getPrevious() gets ...
5
votes
2answers
18k views

Producing every string of a given length using some range of characters

Ever since I was a kid I wanted to understand how brute force programs work. I have not been able to make sense of any of the examples throughout the internet, so it became a personal challenge to ...
5
votes
2answers
3k views

Read file line-by-line with circular buffer

This isn't too complicated but I usually code in C++ instead of C. Doing memory management and IO in C always makes me feel like I'm doing everything wrong and making a mess. This is a small sample ...
5
votes
1answer
702 views

Non blocking single producer/consumer queue with C++11 atomics

I've recently got interested in lockless programming, mainly lockless queues for job repartitions, so here I undertook a challenge of creating lockless queue for single producer and consumer. This is ...
5
votes
1answer
343 views

Lockless, blocking, non synchronized multiple producers and consumers ring buffer

My program is structured like this: there are M producer threads, each of which computes a section of an object O with index <...
5
votes
1answer
549 views

Microcontroller ringbuffer

I'm pretty new to microcontrollers and C in general, so I thought asking here would be a good way not to get started with bad habits. ...