Doubly Linked List (רשימה מקושרת דו כיוונית)

1class Node:2    def __init__(self, value):3        self.value = value4        self.prev = None5        self.next = None6
7
8class DoublyLinkedList:9    def __init__(self):10        self.head = None11        self.tail = None12
13    def append(self, value):14        node = Node(value)15        if self.tail is None:16            self.head = self.tail = node17            return18        # Wire both directions: old tail <-> new node19        node.prev = self.tail20        self.tail.next = node21        self.tail = node22
23    def prepend(self, value):24        node = Node(value)25        if self.head is None:26            self.head = self.tail = node27            return28        node.next = self.head29        self.head.prev = node30        self.head = node31
32    def forward(self):33        values, current = [], self.head34        while current:35            values.append(current.value)36            current = current.next37        return values38
39    def backward(self):40        values, current = [], self.tail41        while current:42            values.append(current.value)43            current = current.prev44        return values45
46
47lst = DoublyLinkedList()48for value in [2, 3, 4]:49    lst.append(value)50lst.prepend(1)51
52print("Forward: ", lst.forward())53print("Backward:", lst.backward())

1class Node {2    constructor(value) {3        this.value = value;4        this.prev = null;5        this.next = null;6    }7}8
9class DoublyLinkedList {10    constructor() {11        this.head = null;12        this.tail = null;13    }14
15    // Tail pointer makes append O(1)16    append(value) {17        const node = new Node(value);18        if (!this.tail) {19            this.head = node;20            this.tail = node;21            return;22        }23        node.prev = this.tail;24        this.tail.next = node;25        this.tail = node;26    }27
28    forward() {29        const out = [];30        for (let n = this.head; n; n = n.next) out.push(n.value);31        return out;32    }33
34    backward() {35        const out = [];36        for (let n = this.tail; n; n = n.prev) out.push(n.value);37        return out;38    }39}40
41const list = new DoublyLinkedList();42for (const value of [10, 20, 30, 40]) list.append(value);43console.log("Forward: ", list.forward().join(" <-> "));44console.log("Backward:", list.backward().join(" <-> "));

1public class Main {2    static class Node {3        int value;4        Node prev, next;5        Node(int value) { this.value = value; }6    }7
8    static Node head, tail;9
10    static void append(int value) {11        Node node = new Node(value);12        if (head == null) { head = tail = node; return; }13        node.prev = tail;14        tail.next = node;15        tail = node;16    }17
18    // Unlink in O(1) once found: fix both neighbor pointers19    static void delete(int value) {20        for (Node cur = head; cur != null; cur = cur.next) {21            if (cur.value != value) continue;22            if (cur.prev != null) cur.prev.next = cur.next; else head = cur.next;23            if (cur.next != null) cur.next.prev = cur.prev; else tail = cur.prev;24            return;25        }26    }27
28    public static void main(String[] args) {29        append(1);30        append(2);31        append(3);32        append(4);33
34        StringBuilder forward = new StringBuilder("Forward:");35        for (Node cur = head; cur != null; cur = cur.next) forward.append(" ").append(cur.value);36        System.out.println(forward);37
38        StringBuilder backward = new StringBuilder("Backward:");39        for (Node cur = tail; cur != null; cur = cur.prev) backward.append(" ").append(cur.value);40        System.out.println(backward);41
42        delete(3);43        StringBuilder after = new StringBuilder("After delete 3:");44        for (Node cur = head; cur != null; cur = cur.next) after.append(" ").append(cur.value);45        System.out.println(after);46    }47}

1#include <iostream>2
3struct Node {4    int value;5    Node* prev = nullptr;6    Node* next = nullptr;7    explicit Node(int v) : value(v) {}8};9
10struct DoublyLinkedList {11    Node* head = nullptr;12    Node* tail = nullptr;13
14    void append(int value) {15        Node* node = new Node(value);16        if (tail == nullptr) {17            head = tail = node;18            return;19        }20        node->prev = tail;  // link both directions21        tail->next = node;22        tail = node;23    }24
25    void prepend(int value) {26        Node* node = new Node(value);27        if (head == nullptr) {28            head = tail = node;29            return;30        }31        node->next = head;32        head->prev = node;33        head = node;34    }35
36    void printForward() const {37        for (Node* cur = head; cur != nullptr; cur = cur->next) {38            std::cout << cur->value << " <-> ";39        }40        std::cout << "null\n";41    }42
43    void printBackward() const {44        for (Node* cur = tail; cur != nullptr; cur = cur->prev) {45            std::cout << cur->value << " <-> ";46        }47        std::cout << "null\n";48    }49};50
51int main() {52    DoublyLinkedList list;53    for (int value : {10, 20, 30}) list.append(value);54    list.prepend(5);55    std::cout << "Forward:  ";56    list.printForward();57    std::cout << "Backward: ";58    list.printBackward();59    return 0;60}

1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5    int value;6    struct Node* prev;7    struct Node* next;8} Node;9
10Node* head = NULL;11Node* tail = NULL;12
13Node* newNode(int value) {14    Node* n = calloc(1, sizeof(Node));15    n->value = value;16    return n;17}18
19void append(int value) {20    Node* node = newNode(value);21    if (tail == NULL) {22        head = tail = node;23        return;24    }25    node->prev = tail;  // link both directions26    tail->next = node;27    tail = node;28}29
30void prepend(int value) {31    Node* node = newNode(value);32    if (head == NULL) {33        head = tail = node;34        return;35    }36    node->next = head;37    head->prev = node;38    head = node;39}40
41void printForward(void) {42    for (Node* cur = head; cur != NULL; cur = cur->next) {43        printf("%d <-> ", cur->value);44    }45    printf("NULL\n");46}47
48void printBackward(void) {49    for (Node* cur = tail; cur != NULL; cur = cur->prev) {50        printf("%d <-> ", cur->value);51    }52    printf("NULL\n");53}54
55int main(void) {56    int values[] = {10, 20, 30};57    for (int i = 0; i < 3; i++) append(values[i]);58    prepend(5);59    printf("Forward:  ");60    printForward();61    printf("Backward: ");62    printBackward();63    return 0;64}