Data Structures and Algorithms

Last Modified: 2/12/2025

2 Linked Lists

A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.

In the implementation we use a sentinel code. Sentinel code make it easier to reason about code, and also give you specific goals to strive for in making sure your code works.

2.1 Singly Linked List

Singly linked lists contain nodes which have a ‘value’ field as well as ‘next’ field, which points to the next node in line of nodes.


97 collapsed lines
1
import java.util.Iterator;
2

3
public class SLList<T> implements Iterable<T> {
4

5
    /**
6
     * Node class for SLList
7
     */
8
    public static class Node<T> {
9
        public T item;
10
        public Node<T> next;
11

12
        public Node(T i, Node<T> n) {
13
            item = i;
14
            next = n;
15
        }
16
    }
17

18
    private final Node<T> sentinel;
19
    private int size;
20

21
    /**
22
     * Default Constructor for SLList
23
     */
24
    public SLList() {
25
        sentinel = new Node<>(null, null);
26
        size = 0;
27
    }
28

29
    /**
30
     * Constructor for SLList with one element
31
     *
32
     * @param x element to be added
33
     */
34
    public SLList(T x) {
35
        sentinel = new Node<>(null, null);
36
        sentinel.next = new Node<>(x, null);
37
        size = 1;
38
    }
39

40
    /**
41
     * Add element to the front of the list
42
     *
43
     * @param x element to be added
44
     */
45
    public void addFirst(T x) {
46
        sentinel.next = new Node<>(x, sentinel.next);
47
        size += 1;
48
    }
49

50
    /**
51
     * Add element to the end of the list
52
     *
53
     * @param x element to be added
54
     */
55
    public void addLast(T x) {
56
        size += 1;
57
        Node<T> p = sentinel;
58
        while (p.next != null) {
59
            p = p.next;
60
        }
61
        p.next = new Node<>(x, null);
62
    }
63

64
    /**
65
     * Return the size of the list
66
     *
67
     * @return size of the list
68
     */
69
    public int size() {
70
        return size;
71
    }
72

73
    /**
74
     * Iterator implementation for SLList
75
     */
76
    public Iterator<T> iterator() {
77
        return new SLListIterator();
78
    }
79

80
    private class SLListIterator implements Iterator<T> {
81
        private Node<T> p;
82

83
        public SLListIterator() {
84
            p = sentinel.next;
85
        }
86

87
        public boolean hasNext() {
88
            return p != null;
89
        }
90

91
        public T next() {
92
            T returnItem = p.item;
93
            p = p.next;
94
            return returnItem;
95
        }
96
    }
97
}


132 collapsed lines
1
#ifndef SLLIST_H
2
#define SLLIST_H
3

4
#include <iterator>
5

6
template <typename T>
7
class SLList {
8
public:
9
    template <typename U>
10
    struct Node {
11
        U item;
12
        Node* next;
13

14
        Node(U i, Node<U>* n) : item(i), next(n) {}
15
    };
16

17
private:
18
    Node<T>* sentinel;
19
    int size;
20

21
public:
22
    SLList();
23
    explicit SLList(T x);
24
    void addFirst(T x);
25
    void addLast(T x);
26
    [[nodiscard]] int getSize() const;
27
    class iterator;
28
    iterator begin();
29
    iterator end();
30
};
31

32
template <typename T>
33
class SLList<T>::iterator {
34
public:
35
    using iterator_category = std::forward_iterator_tag;
36
    using value_type = T;
37
    using difference_type = std::ptrdiff_t;
38
    using pointer = T*;
39
    using reference = T&;
40

41
private:
42
    Node<T>* current;
43

44
public:
45
    explicit iterator(Node<T>* node) : current(node) {}
46
    T& operator*() const;
47
    T* operator->() const;
48
    iterator& operator++();
49
    bool operator==(const iterator& other) const;
50
    bool operator!=(const iterator& other) const;
51
};
52

53
template <typename T>
54
SLList<T>::SLList() : sentinel(new Node<T>(T(), nullptr)), size(0) {}
55

56
template <typename T>
57
SLList<T>::SLList(T x) : sentinel(new Node<T>(T(), nullptr)), size(1) {
58
    sentinel->next = new Node<T>(x, nullptr);
59
}
60

61
/**
62
 * Add element to the front of the list
63
 */
64
template <typename T>
65
void SLList<T>::addFirst(T x) {
66
    sentinel->next = new Node<T>(x, sentinel->next);
67
    size++;
68
}
69

70
/**
71
 * Add element to the end of the list
72
 */
73
template <typename T>
74
void SLList<T>::addLast(T x) {
75
    size++;
76
    Node<T>* p = sentinel;
77
    while (p->next != nullptr) {
78
        p = p->next;
79
    }
80
    p->next = new Node<T>(x, nullptr);
81
}
82

83
/**
84
 * Return the size of the list
85
 */
86
template <typename T>
87
int SLList<T>::getSize() const {
88
    return size;
89
}
90

91
/**
92
 * Iterator implementation for SLList
93
 */
94
template <typename T>
95
typename SLList<T>::iterator SLList<T>::begin() {
96
    return iterator(sentinel->next);
97
}
98

99
template <typename T>
100
typename SLList<T>::iterator SLList<T>::end() {
101
    return iterator(nullptr);
102
}
103

104
template <typename T>
105
T& SLList<T>::iterator::operator*() const {
106
    return current->item;
107
}
108

109
template <typename T>
110
T* SLList<T>::iterator::operator->() const {
111
    return &(current->item);
112
}
113

114
template <typename T>
115
typename SLList<T>::iterator& SLList<T>::iterator::operator++() {
116
    if (current) {
117
        current = current->next;
118
    }
119
    return *this;
120
}
121

122
template <typename T>
123
bool SLList<T>::iterator::operator==(const iterator& other) const {
124
    return current == other.current;
125
}
126

127
template <typename T>
128
bool SLList<T>::iterator::operator!=(const iterator& other) const {
129
    return !(*this == other);
130
}
131

132
#endif // SLLIST_H


45 collapsed lines
1
class Node:
2
    """Represents a node in the singly linked list."""
3
    def __init__(self, item, next_node):
4
        """Initializes a Node with an item and the next node."""
5
        self.item = item
6
        self.next = next_node
7

8
class SLList:
9
    """Represents a singly linked list."""
10
    def __init__(self, x=None):
11
        """
12
        Initializes an SLList.
13
        If x is provided, initializes the list with one element x.
14
        Uses a sentinel node at the front.
15
        """
16
        self.sentinel = Node(None, None)
17
        self.size_val = 0
18

19
        if x is not None:
20
            self.sentinel.next = Node(x, None)
21
            self.size_val = 1
22

23
    def add_first(self, item):
24
        """Adds an item to the front of the list."""
25
        self.sentinel.next = Node(item, self.sentinel.next)
26
        self.size_val += 1
27

28
    def add_last(self, item):
29
        """Adds an item to the end of the list."""
30
        self.size_val += 1
31
        p = self.sentinel
32
        while p.next is not None:
33
            p = p.next
34
        p.next = Node(item, None)
35

36
    def size(self):
37
        """Returns the number of items in the list."""
38
        return self.size_val
39

40
    def __iter__(self):
41
        """Returns an iterator for the SLList."""
42
        p = self.sentinel.next
43
        while p is not None:
44
            yield p.item
45
            p = p.next