What is a Linked List?

연결 리스트는 각 값이 자체 노드에 저장되는 값의 시퀀스이며, 각 노드는 다음 노드에 대한 포인터를 가집니다. 리스트는 첫 번째 노드(헤드)를 알고 있으며, 거기에서 next 포인터 체인을 따라가면 다른 모든 노드에 도달할 수 있습니다.

배열과 달리 연결 리스트는 단일 연속 메모리 블록이 필요하지 않습니다. 헤드에 항목을 추가하는 것은 O(1)입니다. 단순히 새 노드를 생성하고 현재 헤드를 가리키게 하면 됩니다. 단점은 n번째 항목에 도달하는 것이 O(n)이라는 점인데, 이는 체인을 한 번에 한 노드씩 따라가야 하기 때문입니다.

연결 리스트의 다섯 가지 주요 연산은 다음과 같습니다:

1. AddFirst: 리스트의 맨 앞에 값을 추가합니다.
2. AddLast: 리스트의 맨 뒤에 값을 추가합니다.
3. Get: 주어진 인덱스의 값을 반환합니다.
4. Remove: 주어진 인덱스의 값을 삭제합니다.
5. Size: 현재 저장된 값의 개수를 반환합니다.

먼저 Node 클래스를 만든 다음, 그 위에 LinkedList를 구축해 보겠습니다!