IB Computer Science Topic B4.1.3: Constructing and Applying Linked Lists: Singly, Doubly, and Circular Notes

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    Node head = null;
    Node tail = null;
}

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

void insertAtHead(int data) {
    Node newNode = new Node(data);
    newNode.next = head;             // new node points at the old first node
    head = newNode;                  // the new node becomes the head
    if (tail == null) {
        tail = newNode;              // the list was empty
    }
}

void insertAfter(Node previous, int data) {
    Node newNode = new Node(data);
    newNode.next = previous.next;    // attach to the rest of the list FIRST
    previous.next = newNode;         // only then repoint the previous node
    if (newNode.next == null) {
        tail = newNode;              // inserted at the end
    }
}

def insert_at_head(self, data):
    new_node = Node(data)
    new_node.next = self.head        # new node points at the old first node
    self.head = new_node             # the new node becomes the head
    if self.tail is None:
        self.tail = new_node         # the list was empty

def insert_after(self, previous, data):
    new_node = Node(data)
    new_node.next = previous.next    # attach to the rest of the list FIRST
    previous.next = new_node         # only then repoint the previous node
    if new_node.next is None:
        self.tail = new_node         # inserted at the end

void delete(int target) {
    if (head == null) {
        return;                          // nothing to delete
    }
    if (head.data == target) {           // the head is the target
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return;
    }
    Node current = head;
    while (current.next != null && current.next.data != target) {
        current = current.next;          // keep the predecessor in hand
    }
    if (current.next != null) {
        if (current.next == tail) {
            tail = current;              // the tail is being removed
        }
        current.next = current.next.next;   // bypass the target node
    }
}

def delete(self, target):
    if self.head is None:
        return                            # nothing to delete
    if self.head.data == target:          # the head is the target
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        return
    current = self.head
    while current.next is not None and current.next.data != target:
        current = current.next            # keep the predecessor in hand
    if current.next is not None:
        if current.next is self.tail:
            self.tail = current           # the tail is being removed
        current.next = current.next.next  # bypass the target node

void traverse() {
    Node current = head;
    while (current != null) {
        System.out.println(current.data);
        current = current.next;
    }
}

boolean search(int target) {
    Node current = head;
    while (current != null) {
        if (current.data == target) {
            return true;              // found, stop early
        }
        current = current.next;
    }
    return false;                     // reached the end without a match
}

def traverse(self):
    current = self.head
    while current is not None:
        print(current.data)
        current = current.next

def search(self, target):
    current = self.head
    while current is not None:
        if current.data == target:
            return True               # found, stop early
        current = current.next
    return False                      # reached the end without a match

class DNode {
    int data;
    DNode prev;
    DNode next;

    DNode(int data) {
        this.data = data;
    }
}

void insertAtTail(int data) {
    DNode newNode = new DNode(data);
    newNode.prev = tail;
    if (tail != null) {
        tail.next = newNode;          // old tail now points forwards
    } else {
        head = newNode;               // the list was empty
    }
    tail = newNode;
}

void delete(DNode node) {             // the node reference is already known
    if (node.prev != null) {
        node.prev.next = node.next;
    } else {
        head = node.next;             // the node was the head
    }
    if (node.next != null) {
        node.next.prev = node.prev;
    } else {
        tail = node.prev;             // the node was the tail
    }
}

class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

def insert_at_tail(self, data):
    new_node = DNode(data)
    new_node.prev = self.tail
    if self.tail is not None:
        self.tail.next = new_node     # old tail now points forwards
    else:
        self.head = new_node          # the list was empty
    self.tail = new_node

def delete(self, node):               # the node reference is already known
    if node.prev is not None:
        node.prev.next = node.next
    else:
        self.head = node.next         # the node was the head
    if node.next is not None:
        node.next.prev = node.prev
    else:
        self.tail = node.prev         # the node was the tail

void insertAtTail(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;
        newNode.next = head;          // a single node points at itself
        tail = newNode;
        return;
    }
    newNode.next = head;              // close the loop first
    tail.next = newNode;              // old tail now points at the new node
    tail = newNode;
}

void traverse() {
    if (head == null) {
        return;
    }
    Node current = head;
    do {
        System.out.println(current.data);
        current = current.next;
    } while (current != head);         // stop on returning to the head
}

def insert_at_tail(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        new_node.next = self.head     # a single node points at itself
        self.tail = new_node
        return
    new_node.next = self.head         # close the loop first
    self.tail.next = new_node         # old tail now points at the new node
    self.tail = new_node

def traverse(self):
    if self.head is None:
        return
    current = self.head
    while True:
        print(current.data)
        current = current.next
        if current is self.head:      # stop on returning to the head
            break