linked-list , Find middle element of a double linked list in constant time complexity

## Question:

I am trying to find the middle element of a double linked list in constant time complexity . I came across the following http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/ solution. But I don't understand how to use the middle pointer. Can anyone please help me understand this or give me a better solution .

I've re-written this code in C++ for explanation purposes:

``````#include <iostream>

typedef class Node* PNode;
class Node{
public:
PNode next;
PNode prev;
int data;
Node(){
next = nullptr;
prev = nullptr;
data = 0;
}
};

class List{
private:
//Attributes
PNode mid;
int count;
//Methods
void UpdateMiddle( bool _add );

public:
//Constructors
List(){
mid = nullptr;
count = 0;
}
~List(){
while( head != nullptr ){
this->delmiddle();
std::cout << count << std::endl;
}
}
//Methods
void push( int _data );
void pop();
int findmiddle();
void delmiddle();
};

void List::UpdateMiddle( bool _add ){
if( count == 0 ){
mid = nullptr;
}
else if( count == 1 ){
}
else{
int remainder = count%2;
if( remainder == 0 ){
mid = mid->prev;
}
}
else{
if( remainder == 1 ){
mid = mid->next;
}
}
}
}

void List::push( int _data ){
PNode new_node = new Node();

new_node->data = _data;
new_node->prev = nullptr;

if( head != nullptr ) head->prev = new_node;
count++;

UpdateMiddle( true );
}

void List::pop(){
if( head != nullptr ){
PNode del_node = head;

if( head != nullptr ) head->prev = nullptr;

delete del_node;
count--;
UpdateMiddle(false);
}
else if( count != 0 ){
std::cout << "ERROR";
return;
}
}

int List::findmiddle(){
if( count > 0 ) return mid->data;
else return -1;
}

void List::delmiddle(){
if( mid != nullptr ){
if( count == 1 || count == 2){
this->pop();
}
else{
PNode del_mid = mid;
int remainder = count%2;

if( remainder == 0 ){
mid = del_mid->next;
mid->prev = del_mid->prev;
del_mid->prev->next = mid;
delete del_mid;
count--;
}
else{
mid = del_mid->prev;
mid->next = del_mid->next;
del_mid->next->prev = mid;
delete del_mid;
count--;
}
}
}
}
``````

The push and pop functions are self-explanatory, they add nodes on top of the stack and delete the node on the top. In this code, the function `UpdateMiddle` is in charge of managing the `mid` pointer whenever a node is added or deleted. Its parameter `_add` tells it whether a node has been added or deleted. This info is important when there is more than two nodes.

Note that when the `UpdateMiddle` is called within `push` or `pop`, the counter has already been increased or decreased respectively. Let's start with the base case, where there is 0 nodes. `mid` will simply be a `nullptr`. When there is one node, `mid` will be that one node.

Now let's take the list of numbers "5,4,3,2,1". Currently the mid is 3 and `count`, the amount of nodes, is 5 an odd number. Let's add a 6. It will now be "6,5,4,3,2,1" and `count` will now be 6 an even number. The `mid` should also now be 4, as it is the first in the middle, but it still hasn't updated. However, now if we add 7 it will be "7,6,5,4,3,2,1", the `count` will be 7, an odd number, but notice that the `mid` wont change, it should still be 4.

A pattern can be observed from this. When adding a node, and `count` changes from even to odd, the `mid` stays the same, but from odd to even `mid` changes position. More specifically, it moves one position to the left. That is basically what `UpdateMiddle` does. By checking whether `count` is currently odd or even after adding or deleting a node, it decides if `mid` should be repositioned or not. It is also important to tell whether a node is added or deleted because the logic works in reverse to adding when deleting. This is basically the logic that is being applied in the code you linked.

This algorith works because the position of `mid` should be correct at all times before adding or deleting, and function `UpdateMiddle` assumes that the only changes were the addition or deletion of a node, and that prior to this addition or deletion the position of mid was correct. However, we make sure of this by making the attributes and our function `UpdateMiddle` private, and making it modifiable through the public functions.

# Related:

## Inserting an element into an already sorted linked list

I am creating a function that inserts an element into a linked list in the correct order without resorting the list. Here's the code I have: public void insert(E e) { if (e == null) throw new NullPointerException(); if (head == null) { head = new Node(e, null); count++; }...

## Initializing a pointer to a struct with malloc [duplicate]

This question already has an answer here: How do I modify a pointer that has been passed into a function in C? 5 answers This might be a question with a very simple solution but I can't get my head around it... I'm trying to implement linked list for...

## Why is my linked list only printing last entry?

Im trying to read specific lines from a file and add it to a linked list and then print it out. Code bellow : #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct list { int uid; char* uname; struct list* next; }node; void push(node ** head, int uid ,char* uname)...

## Linked list data edit deletes entire list

My class is asking for a program that is capable of inserting projects (this task is working) and giving an evaluation back to them. The problem is when I try to give an evaluation, the program just deletes the whole list, and I don’t know why. Here is the evaluation...

## Spliting Singly Linked List

I'm trying to split a singly linked list into 2 singly linked list. l1 will get 30% members of l and l2 will get the next 30% of l. I don't know what wrong with my code, so please help me. Thanks. P/s: Sorry for my bad English. #include <iostream>...

## Why does ListIterator provide an index for elements in a LinkedList?

Unlike an ArrayList, a LinkedList can not access an element at a particular point using an index. If this is the case, then what is the point of the ListIterator providing functionality that returns the index of a particular point in a LinkedList? Why would I ever need to know...

## Bubble sort double linked list

Hello everyone I'm trying to sort my double linked list in C using bubble sort algorithm. Here is my code: struct node { unsigned char key; unsigned char num; struct node *left; struct node *right; }; Here is my sort funcion: void sort(int count, struct node *t_node) { struct node...

## Error : Expected expression before 'DATA /* : typedef struct DATA DATA */

I don't know what's the problem here my code. I read some questions of others that had the same problem , but I didn't found an answer. When I try to compile I get this errors : ||In function 'main':| |35|error: expected expression before 'DATA'| ||In function 'lecture_data':| |59|error: expected...

## find element in linked list

There is a data structure providing iterators with the following interface: struct iterator { T value(); void next(); bool isValid(); } How would you design an algorithm which at the end of the loop returns some value from the list with equal probability for each element? The list can be...

## Linked list of pointers C++

I have a list but now I have to link it. Here is my program ( I deleted code inside functions to make my program more easy to read ). #include <iostream> using namespace std; struct Student { char ime[16]; char priimek[16]; char vpisna[10]; char ocenaRV[10]; char ocenaDN[10]; char ocenaKV[10];...

## How to delete doubly linked list data and return it?

template <class T> class Node { public: T data; Node<T>* prev; Node<T>* next; // default constructor (parameterized) template <class T> Node(T value) { data = value; prev = NULL; next = NULL; } }; template <class T> T CircularLinkedList<T>::RemoveAt(int p){ Node<T>* temp = head; if (head == NULL){ return 0;...

## I can't find the pointer error that's causing an intermittent crash. Can you?

This works most of the time, but I get an occasional crash. There's a pointer problem somewhere but I can't see it yet. The code takes words out of a string, and builds a linked list of them. The words have to include adjacent punctuation, but no whitespace. For example,...

## Sending LinkedList of Objects through ObjectInputStream throws exceptions 'NotSerializableException' and 'StreamCorruptedException' [duplicate]

This question already has an answer here: StreamCorruptedException: invalid type code: AC 2 answers I'am writing a simple copy of 'Space Invaders'. I want to add network feature, and atm I have problem with Writing/Reading data. So I have a LinkedList of (objects)Aliens and I want to send this...

public class LinkedList { Node head = null; int nodeCount= 0; int counter = 0; LinkedList() { head = null; } public Node reverseTest(Node L) { if(L == null || L.next ==null) { return L; } Node remainingNode = reverseTest(L.next); Node cur = remainingNode; while(cur.next !=null) { cur=cur.next; } L.next...

## Getting “symbols not found” errors implementing a Stack as Linked List using templates

I'm trying to create a stack using a linked list. I've already got it working using integers, but now I want to implement Templates to it. There are no errors detected before compile, but after running I get these errors: *Undefined symbols for architecture x86_84: "Stack::printStack()", referenced from: _main in...

## Copying a linked list onto another linked list - iteratively - C - understanding the returned list

Trying my hand at linked list problems, and for today I'm trying "given a linked list, copy it to another linked list" For doing this iteratively, The logic would be - Use three pointers - current, newList, newTail. current to keep track of the current node in the given, original...

## Classic List of object in C++ using pointers [closed]

I'd like to make one directional list of objects in C++. I've got 3 classes: BasicMiachine,Desktop,Laptop. Two last classses extends BasicMachine. What I want to do is make a list of object (Desktop,Laptop) using only one list. In Basic Class which is abstract class (because I have declare one method...

## Issues with reversing the linkedlist

I'm trying to learn about linked list and it has been little challenging for me. I'm trying to reverse the link list with recursive method. Here is my code: public class ListNode { Node head = null; int nodeCount= 0; int counter = 0; ListNode(){ head = null; } public...

## Deletion in Link List showing “0”

I cannot figure it out why am getting a 0 when trying to delete the first element of the list? I have inserted 3 elements (7,8,9),when am deleting 8 or 9 its working fine for me ,but when am trying to delete 7(.i.e the first element) irrespective of the no...

## How can I restart a double linked list?

I'm coding a program to multiply two polynomials. I need some advice as to how I can restart the double linked list in the nested while loop in the polyProduct function. I mean, at this point I need to go back to the first position of the list. This is...

## Efficiently adding element to the top of the list

I have an ENUM like this from which I always get what is my localFruit which can be either APPLE or ORANGE or BANANA. public enum Fruits { // it can have more elements here APPLE, ORANGE, BANANA; // some code } So let's say if APPLE is my localFruit,...

## Return type of list front (C++)

So I want to use a list for a part of my program. I'm trying to get acquainted to the library list, so I wrote a quick little program to help myself understand what's going on. It all works properly, but there's one thing I don't understand. According to this:...

## C - Singly linked list - passing a pointer by value vs by reference

typedef struct node { int data; struct node *next; } NODE; NODE* add_head(NODE **phead, int data) { NODE *new = (NODE *)malloc(sizeof(NODE)); new->data = data; new->next = *phead; *phead = new; return new; } NODE* add_tail(NODE **phead, int data) { NODE *p, *new = (NODE *)malloc(sizeof(NODE)); new->data = data; new->next...

## Array of pointers to linked list

I need to know if i want to make an array that every element of the array is a pointer to a linked list and pass the array to a function, the function is void because I need to change the array typedef struct n{ char *S; int num; }list;...

## Junk values in deletion of circular linked list

The structure and function that deletes a node in a circular linked list is as follows: struct node { int data; struct node *next; }; struct node *head = NULL; void add(int n) { struct node *temp=NULL,*trav=head; temp = (struct node*)malloc(sizeof(struct node)); temp->data = n; if(head == NULL) { temp->next...

## What is the idiomatic way to write a linked list with a tail pointer?

As a learning project for Rust, I have a very simple (working, if incomplete) implementation of a singly linked list. The declaration of the structs looks like this: type NodePtr<T> = Option<Box<Node<T>>>; struct Node<T> { data: T, next: NodePtr<T>, } pub struct LinkedList<T> { head: NodePtr<T>, } Implementing size and...

## LRU cache with doubly linked list [closed]

I Wanted to implement a memory cache. Found that LRU algorithm seems to be the good approach with a doubly link list. But I was unable to find any implementation guild related to this. Please advice how to approach for this.

## Using the runner technique for linked list

So, I am facing a doubt here. I was reading the book Cracking the coding Interview. The following text is written over there. Suppose you had a linked list a1->a2....->an->b1->b2....bn, and you want to rearrange it into a1->b1->a2->b2->.....an->bn. You don't know the length of the linked list but all you...

## Mimic a LinkedList with a simple float[]

I have to draw on a SurfaceView the trails of some object moving around. The trail of an object is implemented as a LinkedList of points (a point is a pair of float coordinates on the SurfaceView). The LinkedList is motivated by a behaviour like that public class Trail extends...

## LinkedList iterator remove

I have a question on linkedlist iterator If I'm using next , previous and remove methods for example : name.add("Alvin") name.add("Keven") name.add("Jack") ListIterator<String> iterator = name.listIteraot(); //|AKJ iterator.next(); // A|KJ iterator.next(); // AK|J iterator.add("Nina") // AKN|J iterator.next(); // AKNJ| iterator.remove(); // AKN| In the next and then remove method we...

## How to properly unit-test a linked list (using Python)?

I'm new to TDD. I've created all the main functions (insert, search, remove etc.). This is my insert_beginning() function: def insert_beginning(self, node): ''' Inserts a Node to the beginning of the list. ''' node.set_next(self.head) self.head = node My question is, how do I properly unit-test this function? The only way...

## Deleting multiple nodes from simple linked list on C

I want to delete all nodes that have the same idteam as key, but it will crash... I know it should also free() the memory, but anyway I thought this should work :S //defining the struct struct players { int idplayer; int idteam; struct players *next; }; struct players *first,...

## Recursion of Linked List

When given an array of integers, I'm trying to change each element with the product of the integers before it. For example, int[] array = {2,2,3,4}; is now: {2, 4, 12, 48}; I added each element to a LinkedList, and I'm trying to do this recursively. This is what I...

## Changing nodes in linked list

This is somewhat mind-boggling i will try to explain my doubt. Check this function for example: void snoc(Lint *l, int val){ Lint i, new; new = (Lint) malloc(sizeof(Nodo)); new->value = val; new->next = NULL; i=(*l); while(i->next!=NULL){ i=i->next; } i->next = new; } I understand the concept behind and i have...

## Big-O for 2 dimensional array and Linked list

I've made a game by using 9 linked Lists and the other 1 linked lists gets all the address of the other 9 linked lists. Therefore, something like a 2 dimensional array by using linked list. I'm trying to calculate Big-O that my data structure fits and is better than...

## Removing a node from a LinkedList (C#)

I created a LinkedList class with a function delete to remove a certain node from the list if found, however it's not working: public class LinkedList { public Node head; <...> public void delete(string n) { Node x = search(n); //returns the node to delete or null if not found...

## threads safe linked list fine grained in C

I'm implementing a linked list with fine grained locking, meaning a lock in every node. When I'm adding a new node, I want to pass only 2 arguments: key and value. How can I make sure each node has a different lock? The lock is implemented by pthread_mutex_t. This is...

## C++ Changing from singly linked list to doubly linked list

I wrote this code using singly linked list. Now I want to change it to doubly linked list. I have tried few different things but everything messed up. There are few useless lines in my code, but it is basically a singly linked list. What is the proper way to...

## Error Queue implementation using Linked List

I am trying to impliment Queue using linked list but it goes stops unexpectidly. could not find why? #include <iostream> #include <string> using namespace std; Class Node for creating a node. class Node { public: int data; Node *next; }; Queue Class containing operations for Queue. class Queue{ private: Node*...

## Is there a mistake in this illustration?

In chapter 14.2, page 620, in "Big Java" (International 4th edition), by Cay Horstmann, it is shown how to implement a linked list. The add method of the listIterator looks like this: public void add(Object element) { if(position == null) { addFirst(element); position = first; } else { Node newNode...

## Linked List reversal in C not working

I want to do some operations with linked list in C. I have wrote some functions for this like - Insert at beginning, Insert at tail, Delete from beginning etc. In my code I tried to implement reversal of linked list. But it is not working as expected. It always...

## card game in c, shuffle linked list

I trying to shuffle a linked list in c. My idea was to move the list into an array of card then to shuffle the array and then to put it all back in the linked list. when I do build everything is ok but when id use the debugger...

## Linked list deletion and duplication

In the code I copied newnode to the headnode and also to the temp node. But when I delete an instance of data, it seems to affect the other locations as well. When I freed newnode it also erases the content of head and temp .How is this happening? Though...

## Recursion - nth element from last in a linkedlist

Can someone please explain the following function ? void printNthFromLast(struct node* head, int n) { static int i = 0; if(head == NULL) return; printNthFromLast(head->next, n); if(++i == n) printf("%d", head->data); } I just want to know how order of execution of statements occur in recursion i.e given recursive call...

## reverse a linked list using recursion error

I am understanding recursion and so I tried writing reverse a linked list program. I have written the below function but it says segmentation error (core dumped). void reverse(){ if (head -> next == NULL){ return; } reverse (head -> next); struct node *q = (struct node*) malloc (sizeof(struct node));...

## Find middle element of a double linked list in constant time complexity

I am trying to find the middle element of a double linked list in constant time complexity . I came across the following http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/ solution. But I don't understand how to use the middle pointer. Can anyone please help me understand this or give me a better solution .

## How to conditionally remove an element from a list using an iterator?

Problem: I am writing a simple file manager application. In this program I have a "Directory" class: class Directory { public: Directory(string address, string directoryname) { this->path = address; this->name = directoryname; } string GetFullPath(){ return path == "/" ? path + name : path + "/" + name; }...