Реализация Deque с использованием двусвязного списка


Сложный уровень средний
Часто спрашивают в саман Alation Амазонка American Express Де Шоу Набор фактов Фуркиты GE Healthcare Google Кошелек Oxigen Компания Qualcomm Spotify Sprinklr UHG Optum Wooker Xome ZScaler
Dequeue Связанный список Очередь теория

Постановка задачи

Задача «Реализация Deque с использованием двусвязного списка» гласит, что вам необходимо реализовать следующие функции: Deque или Очередь с двойным окончанием, используя связанный список,

  1. insertFront (x): добавить элемент x в начало Deque
  2. insertEnd (x): добавить элемент x в конец Deque
  3. deleteFront (): удалить элемент с начала Deque
  4. deleteEnd (): удалить элемент с конца Deque
  5. getFront (): вернуть элемент в начале Deque
  6. getEnd (): вернуть элемент в конце Deque
  7. isEmpty (): возвращает, пуста ли Deque
  8. size (): вернуть размер Deque
  9. erase (): удалить все элементы Deque

Пример

insertFront(5)
insertEnd(10)
insertEnd(11)
insertFront(19)
getFront()
getEnd()
deleteEnd()
getEnd()
deleteFront()
getFront()
size()
isEmpty()
erase()
isEmpty()
19
11
10
5
2
false
true

Алгоритм

Для реализации Deque используется двусвязный список. Мы сохраняем два указателя спереди и сзади, где передний указывает на начало двусвязного списка, а задний указывает на конец. Также нам необходимо поддерживать целое size, в котором хранится количество узлов в Deque.

к вставить, удалить или получить элемент с начала мы используем передний указатель.

к вставить, удалить или получить элемент с конца мы используем задний указатель.

Реализация Deque с использованием двусвязного списка

insertFront (x)

Чтобы вставить элемент в начало Deque, выполните следующие действия.

  1. Создайте новый узел с нужным значением и назовите его узлом.
  2. Если передняя часть равна нулю, сделайте переднюю и заднюю равными узлу.
  3. В противном случае вставьте узел перед лицевой стороной и пометьте узел как новый передний.
  4. Размер приращения

Сложность времени O (1)

Псевдокод

Create a new node with required value and call it node
if (front == null) {
  front = rear = node
} else {
  node.next = front
  front.prev = node
  front = node
}
size++

insertEnd (x)

Чтобы вставить элемент в конец Deque, выполните следующие действия.

  1. Создайте новый узел с требуемым значением и назовите его узлом.
  2. Если задняя часть равна нулю, сделайте переднюю и заднюю равными узлу.
  3. В противном случае вставьте узел после заднего и отметьте узел как новый задний.
  4. Размер приращения

Сложность времени O (1)

Псевдокод

Create a new node with required value and call it node
if (rear == null) {
  front = rear = node
} else {
  rear.next = node
  node.prev = rear
  rear = node
}
size++

deleteFront ()

Чтобы удалить элемент перед Deque, выполните следующие действия.

  1. Если передняя часть равна нулю, элемент для удаления отсутствует, просто вернитесь.
  2. Если передний равен заднему, то есть только 1 узел, сделайте передний и задний нулевые.
  3. В противном случае сделайте front равным front.next и удалите front.prev
  4. Уменьшить размер

Сложность времени = O (1)

Псевдокод

if (front == null) {
  return
}
if (front == rear) {
  front = rear = null
} else {
  temp = front
  front = front.next
  front.prev = null
  deallocate space for temp
}
size--

deleteEnd ()

Чтобы удалить элемент из конца Deque, выполните следующие действия.

  1. Если задняя часть равна нулю, удаляемого узла нет, просто вернитесь.
  2. Если задний равен переднему, то есть только один узел, сделайте передний и задний нулевые.
  3. В противном случае сделайте заднюю часть как заднюю.пред и удалите заднюю.следующую.
  4. Уменьшить размер

Сложность времени = O (1)

Псевдокод

if (rear == null) {
  return;
}
if (rear == front) {
  front = rear = null
} else {
  temp = rear
  rear = rear.prev
  rear.next = null
  deallocate space for temp
}
size--

getFront ()

Передний элемент Deque указывается спереди, поэтому, если front не равен нулю, верните front.data

Сложность времени = O (1)

Псевдокод

if (front != null) {
  return front.data
}
return -1

getEnd ()

Конечный элемент Deque указывается задом, поэтому, если заднее значение не равно нулю, верните задние данные

Сложность времени = O (1)

Псевдокод

if (rear != null) {
  return rear.data
}
return -1

пустой()

Если Deque пуста, и передняя, ​​и задняя часть будут равны нулю, поэтому, если передняя часть равна нулю, верните true, иначе верните false.

Сложность времени = O (1)

Псевдокод

if (front == null) {
  return true
}
return false

размер()

Размер Deque хранится в переменной с именем «size», поэтому просто верните размер.

Сложность времени = O (1)

Псевдокод

return size

стереть()

Удаление Deque означает удаление всех узлов Deque. Чтобы удалить все узлы, сделайте следующее:

  1. Установить задний как ноль.
  2. Создайте временный указатель temp, указывающий вперед.
  3. Переместитесь в Deque и повторите шаг 4, то есть пока передняя часть не равна нулю, повторите шаг 4.
  4. Установите темп как передний, передний как передний.следующий и освободите место для темп.
  5. Наконец, установите для temp значение null, а для front - значение null, а для размера установите значение 0.

Сложность времени = На), где n - количество узлов в Deque

Псевдокод

rear = null
Node temp = front
while (front != null) {
  temp = front
  front.prev = null
  front = front.next
  deallocate space for temp
}
temp = front = null
size = 0

Код:

Код Java для реализации Deque с использованием двусвязного списка

class DequeUsingDoublyLinkedList {
    // class representing Node of a doubly linked list
    static class Node {
        int data;
        Node next, prev;

        public Node(int data) {
            this.data = data;
        }
    }

    // front points to start of Deque and rear points to the end of Deque
    private static Node front = null;
    private static Node rear = null;
    private static int size = 0;

    private static void insertFront(int x) {
        // Create a new Node with required parameters
        Node node = new Node(x);
        if (front == null) {
            // This is the first node to be inserted
            front = rear = node;
        } else {
            // Add the node before front
            node.next = front;
            front.prev = node;
            // update front
            front = node;
        }
        // Increment size
        size++;
    }

    private static void insertEnd(int x) {
        // Create a new Node with required parameters
        Node node = new Node(x);
        if (rear == null) {
            // This is the first node to be inserted
            front = rear = node;
        } else {
            // Insert the node after rear
            rear.next = node;
            node.prev = rear;
            // update rear
            rear = node;
        }
        // Increment size
        size++;
    }
    private static void deleteFront() {
        if (front == null) {
            // no node to delete
            return;
        }
        if (front == rear) {
            // only 1 node is present
            front = rear = null;
        } else {
            // delete front and move front ahead
            front = front.next;
            front.prev = null;
            // Garbage Collector will automatically delete first node
            // as no pointer is pointing to it
        }
        // decrement size
        size--;
    }

    private static void deleteEnd() {
        if (rear == null) {
            // no node to delete
            return;
        }
        if (rear == front) {
            // only 1 node is present
            front = rear = null;
        } else {
            // delete rear and move rear backwards
            rear = rear.prev;
            rear.next = null;
            // Garbage Collector will automatically delete last node
            // as no pointer is pointing to it
        }
        // decrement size
        size--;
    }

    private static int getFront() {
        if (front != null) {
            // front points to first element in Deque, return its data
            return front.data;
        }
        // no node is present
        return -1;
    }

    private static int getEnd() {
        if (rear != null) {
            // rear points to last element in Deque, return its data
            return rear.data;
        }
        // no node is present
        return -1;
    }

    private static boolean isEmpty() {
        if (front == null) {
            return true;
        }
        return false;
    }
    
    private static int size() {
        return size;
    }
    
    private static void erase() {
        // mark rear as null
        rear = null;
        // traverse the doubly linked list
        while (front != null) {
            // delete all the prev pointers
            front.prev = null;
            front = front.next;
        }
        // After this deque looks like
        // a -> b -> c -> d ..., all the previous pointers are destroyed
        // No pointer is pointing to a, so Garbage collector will delete the whole Deque
        
        // set size as 0
        size = 0;
    }

    public static void main(String[] args) {
        // Example
        insertFront(5);                 // 5
        insertEnd(10);                  // 5 <-> 10
        insertEnd(11);                  // 5 <-> 10 <-> 11
        insertFront(19);                // 19 <-> 5 <-> 10 <-> 11
        System.out.println(getFront());
        System.out.println(getEnd());
        deleteEnd();                    // 19 <-> 5 <-> 10
        System.out.println(getEnd());
        deleteFront();                  // 5 <-> 10
        System.out.println(getFront());    
        System.out.println(size());
        System.out.println(isEmpty());
        erase();
        System.out.println(isEmpty());
    }
}
19
11
10
5
2
false
true

Код C ++ для реализации Deque с использованием двусвязного списка

#include<bits/stdc++.h> 
using namespace std;

// class representing a tree node
class Node {
    public:
    int data;
    Node *next;
    Node *prev;
    
    Node(int d) {
        data = d;
        next = NULL;
        prev = NULL;
    }
};

// function to create a new node
Node* newNode(int x) {
    Node *node = new Node(x);
    return node;
}

// front points to start of Deque and rear points to the end of Deque
Node *front = NULL;
Node *rear = NULL;
// Variable representing size of Deque
int Size = 0;

void insertFront(int x) {
    // Create a new Node with required parameters
    Node *node = newNode(x);
    if (front == NULL) {
        // This is the first node to be inserted
        front = rear = node;
    } else {
        // Add the node before front
        node->next = front;
        front->prev = node;
        // update front
        front = node;
    }
    // Increment size
    Size++;
}

void insertEnd(int x) {
    // Create a new Node with required parameters
    Node *node = newNode(x);
    if (rear == NULL) {
        // This is the first node to be inserted
        front = rear = node;
    } else {
        // Insert the node after rear
        node->prev = rear;
        rear->next = node;
        // update rear
        rear = node;
    }
    // Increment size
    Size++;
}

void deleteFront() {
    if (front == NULL) {
        // no node to delete
        return;
    }
    if (front == rear) {
        // only 1 node is present
        front = rear = NULL;
    } else {
        // delete front and move front ahead
        Node *temp = front;
        front = front->next;
        front->prev = NULL;
        // deallocate the memory taken by temp
        delete(temp);
    }
    // Decrement size
    Size--;
}

void deleteEnd() {
    if (rear == NULL) {
        // no node to delete
        return;
    }
    if (front == rear) {
        // only 1 node is present
        front = rear = NULL;
    } else {
        // delete rear and move rear backwards
        Node *temp = rear;
        rear = rear->prev;
        rear->next = NULL;
        // deallocate the memory taken by temp
        delete(temp);
    }
    // Decrement size
    Size--;
}

int getFront() {
    if (front != NULL) {
        return front->data;
    }
    return -1;
}

int getEnd() {
    if (rear != NULL) {
        return rear->data;
    }
    return -1;
}

int size() {
    return Size;
}

bool isEmpty() {
    if (front == NULL) {
        return true;
    }
    return false;
}

void erase() {
    // mark rear as null
    rear = NULL;
    // traverse the doubly linked list
    while (front != NULL) {
        Node *temp = front;
        // delete all the prev pointers
        front->prev = NULL;
        front = front->next;
        // Deallocate the memory taken by temp
        delete(temp);
    }
    // Set size as 0
    Size = 0;
}

int main() {
    // Example
    insertFront(5);                 // 5
    insertEnd(10);                  // 5 <-> 10
    insertEnd(11);                  // 5 <-> 10 <-> 11
    insertFront(19);                // 19 <-> 5 <-> 10 <-> 11
    cout<<getFront()<<endl;
    cout<<getEnd()<<endl;
    deleteEnd();                    // 19 <-> 5 <-> 10
    cout<<getEnd()<<endl;
    deleteFront();                  // 5 <-> 10
    cout<<getFront()<<endl;     
    cout<<size()<<endl;
    if (isEmpty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    erase();
    if (isEmpty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
19
11
10
5
2
false
true