Explain what a linked list is and how it is structured.

A linked list is a data structure consisting of nodes, where each node contains data and a reference (or references) to the next (and/or previous) node in the list.

Main types:

• Singly linked list: each node contains data and a reference to the next node.
• Doubly linked list: each node contains references to both the next and previous nodes.

Advantages of linked lists:

• Dynamic resizing.
• Fast insertion and deletion of elements in the middle of the list without shifting other elements.

Disadvantages:

• No direct access by index; to get an element, you need to traverse the list.
• Additional memory for storing references.

Example of a singly linked list node in Swift (iOS):

class ListNode {
    var value: Int
    var next: ListNode?

    init(value: Int) {
        self.value = value
        self.next = nil
    }
}

Linked lists are often used to implement stacks, queues, and other dynamic structures.