ڈبللی لنکڈ لسٹ کا استعمال کرتے ہوئے Deque کا نفاذ


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب اییلیشن ایمیزون امریکن ایکسپریس ڈی ای شا حقیقت فورکائٹس GE صحت کا خیال گوگل آکسیجن والیٹ Qualcomm Spotify چھڑکاؤ یو ایچ جی آپٹیم واکر زوم زیڈ اسکیلر
ڈیکیو لنکڈ لسٹ قطار کی تھیوری اور

مسئلہ یہ بیان

مسئلہ "ڈبللی لنکڈ لسٹ کا استعمال کرتے ہوئے عہدے پر عمل درآمد" مسئلہ یہ بتاتا ہے کہ آپ کو مندرجہ ذیل افعال پر عمل درآمد کرنے کی ضرورت ہے ڈیک یا دوگنا ختم کرکے قطار دوگنا منسلک فہرست,

  1. insertFront (x): ڈیک کے آغاز میں عنصر x شامل کریں
  2. insertEnd (x): Deque کے آخر میں عنصر x شامل کریں
  3. ڈیلیٹ فرنٹ (): ڈیک کے آغاز سے ہی عنصر کو حذف کریں
  4. حذف کریں اور (): ڈیک کے آخر سے عنصر کو حذف کریں
  5. گیٹ فرنٹ (): ڈیک کے آغاز پر عنصر کو لوٹائیں
  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 کو نافذ کرنا۔ ہم سامنے اور عقب میں دو پوائنٹس برقرار رکھتے ہیں ، جہاں فرنٹ پوائنٹس دگنا منسلک فہرست کے سامنے اور آخر تک عقبی پوائنٹس کی طرف اشارہ کرتے ہیں۔ اس کے علاوہ ہمیں ایک برقرار رکھنے کی بھی ضرورت ہے عددی سائز ، جو نو میں نوڈس کی تعداد کو محفوظ کرتا ہے۔

کرنے کے لئے داخل کریں ، حذف کریں، یا شروع کرنے سے ایک عنصر حاصل کریں ہم استعمال کرتے ہیں سامنے پوائنٹر

کرنے کے لئے داخل کریں ، حذف کریں، یا آخر سے ایک عنصر حاصل کریں ہم استعمال کرتے ہیں پیچھے پوائنٹر

ڈبللی لنکڈ لسٹ کا استعمال کرتے ہوئے 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++

داخل کریں (ایکس)

ڈیک کے آخر میں عنصر داخل کرنے کے لئے ، درج ذیل کریں

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

حذف کریں اور ()

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

گیٹ فرنٹ ()

ڈیک کا اگلا عنصر سامنے کی طرف اشارہ کیا جاتا ہے ، لہذا اگر سامنے کالع واپس نہیں ہوتا ہے تو سامنے۔ ڈیٹا

وقت کی پیچیدگی = O (1)

چھدم کوڈ

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

getEnd ()

ڈیک کا آخری عنصر پیچھے کی طرف اشارہ کیا گیا ہے ، لہذا اگر پیچھے کالع نہیں ہے تو پیچھے والا اعداد و شمار ہے

وقت کی پیچیدگی = O (1)

چھدم کوڈ

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

خالی ہے()

اگر ڈیک خالی ہے تو سامنے اور پیچھے کا حصہ دونوں ہی خالی ہوں گے ، لہذا اگر سامنے سرخ ہے تو درست ہے ، ورنہ جھوٹے کو لوٹائیں۔

وقت کی پیچیدگی = O (1)

چھدم کوڈ

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

سائز ()

ڈیک کا سائز متغیر میں 'سائز' کے نام سے ذخیرہ کیا جاتا ہے ، لہذا صرف سائز واپس کریں۔

وقت کی پیچیدگی = O (1)

چھدم کوڈ

return size

مٹانا()

ڈیک کو مٹانے کا مطلب ہے ڈیک کے تمام نوڈس کو حذف کرنا۔ مندرجہ ذیل تمام نوڈس کو حذف کرنے کیلئے ،

  1. پیچھے کو کالعدم قرار دیں۔
  2. سامنے کی طرف اشارہ کرتے ہوئے ایک عارضی پوائنٹر ٹمپ بنائیں۔
  3. Deque میں عبور کریں اور مرحلہ 4 کو دہرائیں ، یعنی یہ ہے کہ ، جبکہ سامنے کالعدم اعادہ مرحلہ 4 نہیں ہے۔
  4. عارضی طور پر سامنے کے سامنے ، سامنے کے طور پر سامنے مقرر کریں۔
  5. آخر کار کال کے طور پر ٹھوکر اور سامنے کو کالعدم اور سائز کو 0 کی حیثیت سے مقرر کریں۔

وقت کی پیچیدگی = O (n) ، جہاں 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

ضابطے

ڈبللی لنکڈ لسٹ کا استعمال کرتے ہوئے ڈیکو کے نفاذ کے لئے جاوا کوڈ

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 ++ کوڈ

#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