د ډبل تړلي لیست په کارولو سره د تقویم پلي کول


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ایڈوب ایلیشن ترلاسه کړئ Amazon د امریکا د اکسپرس DE شا حقیقت څلورکیټونه په روبل روغتيا د ګوګل د آکسیجن والټ Qualcomm Spotify سپرینکلر د UHG Optum ووکر زوم ZScaler
Dequeue تړلي لیست په ليکه کې تیوری

ستونزه بیان

ستونزه "د دوه ګوني تړل شوي لیست په کارولو سره د تقویم پلي کول" په ګوته کوي چې تاسو اړتیا لرئ د لاندې فعالیتونو پلي کولو ته اړتیا ولرئ ډیک یا دوه ځله په دوه ځله کارولو سره قطعه ختمه شوه تړلي لیست,

  1. insertFront (x): د ډیک په پیل کې عنصر ایکس اضافه کړئ
  2. insertEnd (x): د ډیک په پای کې ایکس عنصر اضافه کړئ
  3. حذف شوی (): د ډیک له پیل څخه یو عنصر حذف کړئ
  4. حذف او (): د ډیک پای څخه عنصر حذف کړئ
  5. getFront (): عنصر د Deque په پیل کې بیرته راګرځئ
  6. getEnd (): عنصر د ډیک په پای کې راستن کړئ
  7. isEmpty (): بیرته راګرځي که Deque خالي وي
  8. کچه (): د Deque اندازه بیرته راشئ
  9. پاکول (): د 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 پلي کول. موږ دوه نښې مخکیني او شا ساتو ، چیرې چې د دوه ځلې تړل شوي لیست مخ ته اشاره کوي او پای ته د شا ټکي. همدارنګه موږ اړتیا لرو چې ساتنه وکړو ضمیمه اندازه ، کوم چې په ډیک کې د نوډونو شمیر ساتي.

ته دننه کړئ ، حذف کړئ، او یا د پیل څخه یو عنصر ترلاسه کړئ موږ د مخ نغوت

ته دننه کړئ ، حذف کړئ، او یا د پای نه یو عنصر ترلاسه کړه موږ د شا نغوت

د ډبل تړلي لیست په کارولو سره د تقویم پلي کول

insertFront (x)

د ډیک مخې ته د عنصر دننه کولو لپاره ، لاندې ترسره کړئ

  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++

داخل کړئ (x)

د ډیک په پای کې د عنصر دننه کولو لپاره ، لاندې ترسره کړئ

  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++

ړنګول ()

د Deque مخې څخه د عنصر حذف کولو لپاره ، لاندې ترسره کړئ

  1. که مخ خالي وي ، د حذف کولو لپاره هیڅ عنصر شتون نلري ، په ساده ډول بیرته.
  2. که چیرې مخکینۍ مساوي وي ، نو یوازې 1 نوډ شتون لري ، مخ او شا غوطه جوړه کړئ.
  3. بل ، د مخ برابر مساوي جوړ کړئ. مخ او ړنګ کړئ
  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--

ړنګول ()

د ډیک پای څخه د عنصر حذف کولو لپاره ، لاندې ترسره کړئ

  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--

ګیټ فرنټ ()

د ډیک فني عنصر د مخ په ګوته کیږي ، نو که چیرې مخ بیرته نه وي نو فرنټ.ډټا

د وخت پیچلتیا = O (1)

د جعلي کوډ

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

ترلاسه کړئ او ()

د ډیک پای عنصر د شا لخوا اشاره شوی ، نو که چیرې شا پاک نه وي رییر.ډاټا

د وخت پیچلتیا = O (1)

د جعلي کوډ

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

ای ایم پیټي ()

که چیرې ډیک خالي وي دواړه مخ او شیان به خالي وي ، نو که مخ بیرته خالي وي ریښتیني وي ، نو غلط ته راستون شئ.

د وخت پیچلتیا = O (1)

د جعلي کوډ

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

اندازه ()

د ډیک اندازه د 'اندازې' په نوم تغیر کې زیرمه شوې ، نو په اسانۍ سره اندازه بیرته راستون کړئ.

د وخت پیچلتیا = O (1)

د جعلي کوډ

return size

پاکول ()

د ډیک له مینځه وړلو معنی ده د Deque ټول نوډونه حذف کول. د ټولو نوډونو حذف کولو لپاره لاندې چارې ترسره کړئ ،

  1. شات د باطل په توګه وټاکئ.
  2. لنډمهاله پوائنټر ټیم جوړ کړئ ، مخ ته په نښه کول.
  3. په ډیک کې تکرار کړئ او څلورم ګام تکرار کړئ ، دا دی ، پداسې حال کې چې مخ ناڅاپي 4 ګام ندی.
  4. د ټیم لپاره د مخې په څیر ، دمخه دمخه په ترتیب کړئ. دمخه او د ټیم لپاره د ځای ضایع کول.
  5. په نهایت کې لنډ د خالي او مخکښې په توګه د خالي او اندازه اندازه د 0 په توګه تنظیم کړئ.

د وخت پیچلتیا = O (n) ، چیرې چې n په ډیک کې د نوډونو شمیر دی

د جعلي کوډ

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

کوډ

د ډبللي تړلي لیست په کارولو سره د 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

د ډبللي تړلي لیست په کارولو سره د Dequ پلي کولو لپاره C ++ کوډ

#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