LinkedList

A linked list is a linear data structure that consists of a sequence of nodes, where each node contains data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, allowing for dynamic memory usage and efficient insertion and deletion operations.

the props of linked list:

  • Dynamic size: Linked lists can grow or shrink in size as needed, without the need for contiguous memory allocation.
  • Efficient insertion and deletion: Inserting or deleting a node in a linked list can be done in constant time O(1) if the reference to the node is known, as it only requires updating the links between nodes.
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
class Node:
    def __init__(self, data， next=None):
        self.data = data
        self.next = next

class LinkedList:
    def __init__(self):
        self.__head = None
        self.__size = 0

    def __str__(self):
        result = []
        current = self.__head
        while current:
            result.append(str(current.data))
            current = current.next
        return " -> ".join(result)

    @property
    def size(self):
        return self.__size

    def is_empty(self):
        return self.__size == 0

    def insert(self, index, data):
        if index < 0 or index > self.size:
            raise IndexError("Index out of bounds")

        if index == 0:
            self.__head = Node(data， self.__head)
        else:
            current = self.__head
            for _ in range(index - 1):
                current = current.next
            current.next = Node(data， current.next)
        self.__size += 1

    def append(self, data):
        self.insert(self.__size, data)

    def remove(self, index):
        if index < 0 or index >= self.__size:
            raise IndexError("Index out of bounds")
        if index == 0:
            self.__head = self.__head.next
        else:
            current = self.__head
            for _ in range(index - 1):
                current = current.next
            current.next = current.next.next
        self.__size -= 1

    def set(self, index, data):
        if index < 0 or index >= self.__size:
            raise IndexError("Index out of bounds")
        current = self.__head
        for _ in range(index):
            current = current.next
        current.data = data

    def get(self, index):
        if index < 0 or index >= self.__size:
            raise IndexError("Index out of bounds")
        current = self.__head
        for _ in range(index):
            current = current.next
        return current.data

    def find(self, data):
        current = self.__head
        for index in range(self.__size):
            if current.data == data:
                return index
            current = current.next
        return -1

    def forEach(self, func):
        current = self.__head
        while current:
            func(current.data)
            current = current.next