Skip to content

Linked Lists

Linked Lists are dynamic data structures that provide efficient insertion and deletion at arbitrary positions. Harneet's LinkedList implementation uses doubly-linked nodes for bidirectional traversal and O(1) operations at both ends.

Overview

A LinkedList stores elements in nodes that contain: - The element value - A pointer to the next node - A pointer to the previous node (doubly-linked)

This structure allows for: - Dynamic size adjustment - Efficient insertion/deletion at any position - Bidirectional iteration - O(1) operations at head and tail

Creating a LinkedList

Creating a LinkedList
1
2
3
import collections

var list = collections.new_linked_list()

Basic Operations

Adding Elements

Add to Front (Head)

Add to Front
1
2
3
4
5
6
7
8
var list = collections.new_linked_list()

list.add_first("first")
list.add_first("second")
list.add_first("third")

fmt.Println("List:", list.inspect())  // [third, second, first]
fmt.Println("Size:", list.size())     // 3

Add to Back (Tail)

Add to Back
1
2
3
4
list.add_last("fourth")
list.add_last("fifth")

fmt.Println("List:", list.inspect())  // [third, second, first, fourth, fifth]

Add at Specific Position

Add at Position
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// Insert at index 2 (0-based)
var success = list.add_at(2, "inserted")
if success {
    fmt.Println("After insertion:", list.inspect())  // [third, second, inserted, first, fourth, fifth]
}

// Error handling for invalid positions
var result = list.add_at(100, "invalid")
if result.type() == "ERROR" {
    fmt.Println("Cannot insert at invalid position")
}

Removing Elements

Remove from Front

Remove from Front
1
2
3
4
5
if !list.is_empty() {
    var first = list.remove_first()
    fmt.Println("Removed first:", first)  // "third"
    fmt.Println("List:", list.inspect())
}

Remove from Back

Remove from Back
1
2
3
4
5
if !list.is_empty() {
    var last = list.remove_last()
    fmt.Println("Removed last:", last)   // "fifth"
    fmt.Println("List:", list.inspect())
}

Remove at Specific Position

Remove at Position
1
2
3
4
5
6
// Remove element at index 1
if list.size() > 1 {
    var removed = list.remove_at(1)
    fmt.Println("Removed at index 1:", removed)
    fmt.Println("List:", list.inspect())
}

Remove by Value

Remove by Value
1
2
var found = list.remove("inserted")
fmt.Println("Removed 'inserted':", found)  // true if found and removed

Accessing Elements

Get by Index

Get by Index
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// Access elements by position
if list.size() > 0 {
    var first = list.get(0)
    fmt.Println("First element:", first)

    var last = list.get(list.size() - 1)
    fmt.Println("Last element:", last)
}

// Error handling for invalid indices
var result = list.get(-1)
if result.type() == "ERROR" {
    fmt.Println("Invalid index")
}

Find Element Position

Find Element Position
1
2
3
4
5
6
7
8
9
var index = list.index_of("first")
if index != -1 {
    fmt.Println("'first' found at index:", index)
} else {
    fmt.Println("'first' not found")
}

// Find last occurrence
var last_index = list.last_index_of("duplicate")

List Information

List Information
1
2
3
4
5
6
7
fmt.Println("Size:", list.size())
fmt.Println("Is empty:", list.is_empty())
fmt.Println("Contains 'first':", list.contains("first"))

// Clear all elements
list.clear()
fmt.Println("After clear:", list.is_empty())  // true

Iteration and Traversal

Forward Iteration

Forward Iteration
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
var numbers = collections.new_linked_list()
for i in range(1, 6) {
    numbers.add_last(i)
}

// Using iterator
var iter = numbers.iterator()
fmt.Println("Forward iteration:")
for iter.has_next() {
    var item = iter.next()
    fmt.Println("  Item:", item)
}

Reverse Iteration

Reverse Iteration
1
2
3
4
5
6
7
// Using reverse iterator
var reverse_iter = numbers.reverse_iterator()
fmt.Println("Reverse iteration:")
for reverse_iter.has_next() {
    var item = reverse_iter.next()
    fmt.Println("  Item:", item)
}

For-Each Style Iteration

For-Each Iteration
1
2
3
4
5
6
7
// If supported by language
for item in numbers {
    fmt.Println("Item:", item)
}

// Functional style
numbers.for_each(((item) =>) fmt.Println("Item:", item))

Advanced Features

Conversion Operations

Conversion Operations
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
var list = collections.new_linked_list()
list.add_last("a")
list.add_last("b")
list.add_last("c")

// Convert to array
var array = list.to_array()
fmt.Println("As array:", array)

// Create from array
var from_array = collections.linked_list_from_array([1, 2, 3, 4])

Functional Operations

Functional Operations
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
var numbers = collections.new_linked_list()
for i in range(1, 11) {
    numbers.add_last(i)
}

// Map elements (creates new list)
var doubled = numbers.map(((n) =>) n * 2)
fmt.Println("Doubled:", doubled.inspect())

// Filter elements
var evens = numbers.filter(((n) =>) n % 2 == 0)
fmt.Println("Evens:", evens.inspect())

// Reduce to single value
var sum = numbers.reduce(|acc, n| acc + n, 0)
fmt.Println("Sum:", sum)

// Find first matching element
var first_even = numbers.find(((n) =>) n % 2 == 0)
fmt.Println("First even:", first_even)

List Manipulation

List Manipulation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var list1 = collections.new_linked_list()
list1.add_last("a")
list1.add_last("b")

var list2 = collections.new_linked_list()
list2.add_last("c")
list2.add_last("d")

// Concatenate lists
var combined = list1.concat(list2)
fmt.Println("Combined:", combined.inspect())  // [a, b, c, d]

// Reverse list in place
list1.reverse()
fmt.Println("Reversed:", list1.inspect())    // [b, a]

// Sort list (if elements are comparable)
var unsorted = collections.linked_list_from_array([3, 1, 4, 1, 5])
unsorted.sort()
fmt.Println("Sorted:", unsorted.inspect())   // [1, 1, 3, 4, 5]

// Sort with custom comparator
unsorted.sort_by(|a, b| b - a)  // Descending order
fmt.Println("Desc sorted:", unsorted.inspect())  // [5, 4, 3, 1, 1]

Use Cases and Examples

1. Undo/Redo System

Undo/Redo System
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
struct Command {
    action: string
    data: any
    undo_data: any
}

struct UndoRedoManager {
    undo_stack: LinkedList
    redo_stack: LinkedList
    max_history: int
}

function new_undo_manager(max_history) {
    return UndoRedoManager{
        undo_stack: collections.new_linked_list(),
        redo_stack: collections.new_linked_list(),
        max_history: max_history
    }
}

function (um *UndoRedoManager) execute_command(command) {
    // Execute the command
    fmt.Println("Executing:", command.action)

    // Add to undo stack
    um.undo_stack.add_last(command)

    // Clear redo stack (new action invalidates redo history)
    um.redo_stack.clear()

    // Limit history size
    if um.undo_stack.size() > um.max_history {
        um.undo_stack.remove_first()
    }
}

function (um *UndoRedoManager) undo() {
    if !um.undo_stack.is_empty() {
        var command = um.undo_stack.remove_last()
        fmt.Println("Undoing:", command.action)

        // Add to redo stack
        um.redo_stack.add_last(command)

        return command
    }
    return null
}

function (um *UndoRedoManager) redo() {
    if !um.redo_stack.is_empty() {
        var command = um.redo_stack.remove_last()
        fmt.Println("Redoing:", command.action)

        // Add back to undo stack
        um.undo_stack.add_last(command)

        return command
    }
    return null
}

// Usage
var manager = new_undo_manager(10)
manager.execute_command(Command{action: "create_file", data: "file1.txt"})
manager.execute_command(Command{action: "edit_file", data: "content"})
manager.undo()  // Undo edit
manager.undo()  // Undo create
manager.redo()  // Redo create

2. Music Playlist

Music Playlist
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
struct Song {
    title: string
    artist: string
    duration: int  // seconds
}

struct Playlist {
    songs: LinkedList
    current_position: int
    name: string
}

function new_playlist(name) {
    return Playlist{
        songs: collections.new_linked_list(),
        current_position: -1,
        name: name
    }
}

function (p *Playlist) add_song(song) {
    p.songs.add_last(song)
}

function (p *Playlist) insert_song(position, song) {
    if position >= 0 && position <= p.songs.size() {
        p.songs.add_at(position, song)
        // Adjust current position if needed
        if position <= p.current_position {
            p.current_position = current_position + 1
        }
    }
}

function (p *Playlist) remove_song(position) {
    if position >= 0 && position < p.songs.size() {
        var removed = p.songs.remove_at(position)
        // Adjust current position
        if position < p.current_position {
            p.current_position--
        } else if position == p.current_position {
            p.current_position = -1  // Current song removed
        }
        return removed
    }
    return null
}

function (p *Playlist) next_song() {
    if p.current_position < p.songs.size() - 1 {
        p.current_position = current_position + 1
        return p.songs.get(p.current_position)
    }
    return null  // End of playlist
}

function (p *Playlist) previous_song() {
    if p.current_position > 0 {
        p.current_position--
        return p.songs.get(p.current_position)
    }
    return null  // Beginning of playlist
}

function (p *Playlist) shuffle() {
    // Convert to array, shuffle, convert back
    var array = p.songs.to_array()
    array.shuffle()
    p.songs = collections.linked_list_from_array(array)
    p.current_position = -1
}

function (p *Playlist) get_total_duration() {
    return p.songs.reduce(|acc, song| acc + song.duration, 0)
}

// Usage
var playlist = new_playlist("My Favorites")
playlist.add_song(Song{title: "Song 1", artist: "Artist A", duration: 180})
playlist.add_song(Song{title: "Song 2", artist: "Artist B", duration: 210})
playlist.add_song(Song{title: "Song 3", artist: "Artist C", duration: 195})

var current = playlist.next_song()
fmt.Println("Now playing:", current.title)

playlist.shuffle()
fmt.Println("Playlist shuffled")

3. Browser History

Browser History
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
struct BrowserHistory {
    history: LinkedList
    current_index: int
    max_history: int
}

function new_browser_history(max_history) {
    return BrowserHistory{
        history: collections.new_linked_list(),
        current_index: -1,
        max_history: max_history
    }
}

function (bh *BrowserHistory) visit(url) {
    // Remove any forward history when visiting new page
    for bh.current_index < bh.history.size() - 1 {
        bh.history.remove_last()
    }

    // Add new page
    bh.history.add_last(url)
    bh.current_index = current_index + 1

    // Limit history size
    if bh.history.size() > bh.max_history {
        bh.history.remove_first()
        bh.current_index--
    }

    fmt.Println("Visited:", url)
}

function (bh *BrowserHistory) back() {
    if bh.current_index > 0 {
        bh.current_index--
        var url = bh.history.get(bh.current_index)
        fmt.Println("Back to:", url)
        return url
    }
    fmt.Println("Cannot go back")
    return null
}

function (bh *BrowserHistory) forward() {
    if bh.current_index < bh.history.size() - 1 {
        bh.current_index = current_index + 1
        var url = bh.history.get(bh.current_index)
        fmt.Println("Forward to:", url)
        return url
    }
    fmt.Println("Cannot go forward")
    return null
}

function (bh *BrowserHistory) current_url() {
    if bh.current_index >= 0 && bh.current_index < bh.history.size() {
        return bh.history.get(bh.current_index)
    }
    return null
}

function (bh *BrowserHistory) get_history() {
    return bh.history.to_array()
}

// Usage
var browser = new_browser_history(50)
browser.visit("https://example.com")
browser.visit("https://example.com/page1")
browser.visit("https://example.com/page2")
browser.back()     // Back to page1
browser.back()     // Back to example.com
browser.forward()  // Forward to page1
browser.visit("https://different.com")  // Clears forward history

4. Text Editor with Line Management

Text Editor
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
struct TextLine {
    content: string
    line_number: int
}

struct TextEditor {
    lines: LinkedList
    cursor_line: int
    file_name: string
}

function new_text_editor(file_name) {
    return TextEditor{
        lines: collections.new_linked_list(),
        cursor_line: 0,
        file_name: file_name
    }
}

function (te *TextEditor) insert_line(line_number, content) {
    var text_line = TextLine{content: content, line_number: line_number}

    if line_number >= te.lines.size() {
        te.lines.add_last(text_line)
    } else {
        te.lines.add_at(line_number, text_line)
    }

    // Update line numbers
    te.update_line_numbers()
}

function (te *TextEditor) delete_line(line_number) {
    if line_number >= 0 && line_number < te.lines.size() {
        te.lines.remove_at(line_number)
        te.update_line_numbers()

        // Adjust cursor
        if te.cursor_line >= te.lines.size() {
            te.cursor_line = te.lines.size() - 1
        }
    }
}

function (te *TextEditor) get_line(line_number) {
    if line_number >= 0 && line_number < te.lines.size() {
        return te.lines.get(line_number)
    }
    return null
}

function (te *TextEditor) update_line_numbers() {
    var iter = te.lines.iterator()
    var line_num = 0
    for iter.has_next() {
        var line = iter.next()
        line.line_number = line_num
        line_num = line_num + 1
    }
}

function (te *TextEditor) find_text(search_text) {
    var results = collections.new_linked_list()
    var iter = te.lines.iterator()

    for iter.has_next() {
        var line = iter.next()
        if line.content.contains(search_text) {
            results.add_last(line.line_number)
        }
    }

    return results.to_array()
}

function (te *TextEditor) get_text() {
    var content = ""
    var iter = te.lines.iterator()

    for iter.has_next() {
        var line = iter.next()
        content += line.content + "\n"
    }

    return content
}

// Usage
var editor = new_text_editor("example.txt")
editor.insert_line(0, "First line")
editor.insert_line(1, "Second line")
editor.insert_line(1, "Inserted line")  // Becomes line 1, pushes others down

var found_lines = editor.find_text("line")
fmt.Println("Lines containing 'line':", found_lines)

fmt.Println("Full text:")
fmt.Println(editor.get_text())

Performance Characteristics

Time Complexity

Operation Time Complexity Notes
Add First/Last O(1) Direct head/tail access
Remove First/Last O(1) Direct head/tail access
Add/Remove At Index O(n) Must traverse to position
Get by Index O(n) Must traverse to position
Search (indexOf) O(n) Linear search required
Size O(1) Cached counter
Is Empty O(1) Simple size check
Clear O(1) Reset pointers, GC handles cleanup

Space Complexity

  • Storage: O(n) where n is the number of elements
  • Node Overhead: Each node requires additional memory for next/prev pointers
  • Memory Layout: Non-contiguous memory allocation (cache-unfriendly for traversal)

When to Use LinkedList vs Array

Use LinkedList when: - Frequent insertion/deletion at arbitrary positions - Size varies significantly during runtime - You need efficient head/tail operations - Memory usage is more important than cache performance

Use Array when: - Frequent random access by index - Cache performance is critical - Memory overhead should be minimal - Size is relatively stable

Error Handling

LinkedLists handle errors consistently:

Error Handling
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
var list = collections.new_linked_list()

// Index out of bounds
var result = list.get(10)
if result.type() == "ERROR" {
    fmt.Println("Index out of bounds")
}

// Safe operations
if !list.is_empty() {
    var item = list.remove_first()  // Safe
}

// Bounds checking
if index >= 0 && index < list.size() {
    var item = list.get(index)  // Safe
}

// Null handling
list.add_last(null)  // null values are allowed
fmt.Println("Contains null:", list.contains(null))

Best Practices

1. Use Appropriate Access Patterns

Appropriate Access Patterns
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Efficient: head/tail operations
list.add_first(item)    // O(1)
list.add_last(item)     // O(1)
list.remove_first()     // O(1)
list.remove_last()      // O(1)

// Less efficient: middle operations
list.add_at(middle, item)     // O(n)
list.remove_at(middle)        // O(n)
list.get(middle)              // O(n)

2. Use Iterators for Traversal

Use Iterators
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// Efficient iteration
var iter = list.iterator()
for iter.has_next() {
    var item = iter.next()
    // Process item
}

// Avoid index-based loops
for i in range(list.size()) {
    var item = list.get(i)  // O(n) for each access = O(n²) total
}

3. Consider Memory Usage

Consider Memory Usage
1
2
3
4
5
// LinkedList has higher memory overhead
var list = collections.new_linked_list()  // Each node has pointer overhead

// For simple sequential access, consider arrays
var array = collections.new_array()       // Contiguous memory, better cache performance

4. Use Functional Methods When Available

Use Functional Methods
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Instead of manual loops
var result = collections.new_linked_list()
for item in original_list {
    if condition(item) {
        result.add_last(transform(item))
    }
}

// Use functional methods
var result = original_list.filter(condition).map(transform)

5. Handle Concurrent Access

Handle Concurrent Access
1
2
3
// For concurrent access, use appropriate synchronization
var shared_list = collections.new_linked_list()
// Add proper locking or use concurrent collections

LinkedLists provide flexible, dynamic storage with efficient insertion and deletion capabilities, making them ideal for scenarios where the data structure size and content change frequently during program execution.