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


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

Question:

Tag: linked-list

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 .


Answer:

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 head;
    PNode mid;
    int count;
    //Methods
    void UpdateMiddle( bool _add );

public:
    //Constructors 
    List(){
        head = nullptr;
        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 ){
        mid = head;
    }
    else{
        int remainder = count%2;
        if(_add){
            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;
    new_node->next = head;

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

    UpdateMiddle( true );
}

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

        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:


Is there a mistake in this illustration?


java,data-structures,linked-list,singly-linked-list
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...

Junk values in deletion of circular linked list


c,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...

card game in c, shuffle linked list


c,linked-list,shuffle,realloc
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...

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


c,pointers,linked-list
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...

LRU cache with doubly linked list [closed]


java,algorithm,linked-list,lru
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


algorithm,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...

Big-O for 2 dimensional array and Linked list


c++,c,arrays,linked-list,big-o
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...

Issues with reversing the linkedlist


java,algorithm,linked-list,nodes
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...

Recursion - nth element from last in a linkedlist


c,recursion,linked-list
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...

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


c++,linked-list,listiterator
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; }...

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


linked-list,rust,reference-counting
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...

Recursion of Linked List


java,recursion,nullpointerexception,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...

Efficiently adding element to the top of the list


java,list,arraylist,enums,linked-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,...

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


java,sockets,exception,linked-list,network-programming
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...

Deleting multiple nodes from simple linked list on C


c,list,linked-list,nodes,erase
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,...

find element in linked list


algorithm,linked-list,computer-science
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...

Deletion in Link List showing “0”


c++,linked-list
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...

Removing a node from a LinkedList (C#)


c#,data-structures,linked-list,hashtable
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...

Linked List reversal in C not working


c,linked-list,singly-linked-list
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...

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


c++,templates,linked-list,stack
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...

threads safe linked list fine grained in C


c,multithreading,linked-list
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...

Mimic a LinkedList with a simple float[]


java,android,arrays,linked-list
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...

How can I restart a double linked list?


c,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...

Array of pointers to linked list


c,arrays,pointers,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;...

Linked list data edit deletes entire list


c++,linked-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...

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


c,algorithm,linked-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...

LinkedList Recursion


java,linked-list
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...

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


c++,linked-list,singly-linked-list,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...

Why is my linked list only printing last entry?


c,file,linked-list
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)...

Spliting Singly Linked List


c++,linked-list,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>...

Bubble sort double linked list


c,sorting,linked-list,bubble-sort
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 */


c,struct,compiler-errors,linked-list,typedef
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...

Error Queue implementation using Linked List


c++,data-structures,linked-list,queue
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*...

reverse a linked list using recursion error


c,recursion,linked-list
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));...

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


c++,pointers,linked-list
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...

LinkedList iterator remove


java,linked-list,delete,iterator
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...

<< Definition using inheritance and templates [duplicate]


c++,templates,visual-studio-2012,linked-list
This question already has an answer here: What is an undefined reference/unresolved external symbol error and how do I fix it? 18 answers I am trying to implement a Linked List in C++ using templates. Unfortunately I am getting an unresolved external error when I try to use a...

Inserting an element into an already sorted linked list


java,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++; }...

Linked list deletion and duplication


c++,c,linked-list
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...

C++ Unable to Print Pointer Data of a Linked List


c++,linked-list,nodes
I'm dealing with a doubly Linked List. It's made up of classes and is centered around the current node (instead of a node in the beginning or end of the list). Now my print function will throw an error but only if I have traversed the list at all. My...

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


linked-list
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 .

Changing nodes in linked list


c,list,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...

How to delete doubly linked list data and return it?


c++,data-structures,linked-list,doubly-linked-list
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;...

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


java,linked-list
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...

Why Linkedlist in hashmap?Why not other implementation of List?


java,arrays,linked-list,hashmap
As HashMap uses LinkedList when two different keys produces a same hashCode.But I was wondering what makes LinkedList a better candidate here over other implementation of List.Why not ArrayList because ArrayList uses Array internally and arrays have a faster iteration compared to a LinkedList.

Initializing a pointer to a struct with malloc [duplicate]


c,pointers,linked-list
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...

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


c,pointers,linked-list
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,...

Return type of list front (C++)


c++,function,reference,linked-list,return-type
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:...

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


python,unit-testing,linked-list
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...

Linked list of pointers C++


c++,linked-list
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];...