리스트 ( List )
- 데이터를 순서대로 저장하는 선형 자료구조
- 인덱스 기반으로 각 요소에 접근 가능
- 일반 배열과 다르게 요소가 추가되어 공간이 부족해지면 자동으로 더 큰 배열을 새로 할당해 기존 요소를 복사함
- 중간 삽입/삭제가 일어나면 ,연속성을 유지하기 위해 연산 부하가 생김 > 삽입/삭제가 된 부분 뒤 요소를 전부 복사해서 땡겨오거나 밀어서 다시 배열을 만드는 방식
- 배열의 크기는 Capacity로 실제 요소의 수는 Count로 알 수 있음
주요 특징 및 성능
| 연산 | 시간 복잡도 | 설명 |
| 요소 접근 (Access) | O(1) |
인덱스를 알면 주소를 바로 계산할 수 있어 매우 빠릅니다.
|
| 끝에 삽입/삭제 | O(1) (평균) |
끝에 추가하는 것은 보통 빠르지만, 배열 크기를 늘려야 할 경우 $O(N)$이 될 수 있습니다.
|
| 중간에 삽입/삭제 | O(N) |
요소를 삽입하거나 삭제할 때, 그 뒤의 모든 요소를 한 칸씩 밀거나 당겨야 하므로 느립니다.
|
| 메모리 | 효율적 |
연속된 공간에 저장되어 메모리 참조 효율(캐시 활용)이 높습니다.
|
자주 사용하는 메서드
1. 요소 추가 및 삽입 (Add & Insert)
| 메서드 | 설명 | 예시 (List<int> numbers) |
| Add(T item) | 리스트의 맨 끝에 요소를 추가합니다. | numbers.Add(10); // [10] |
| AddRange(IEnumerable<T> collection) | 다른 컬렉션(배열, 다른 리스트 등)의 모든 요소를 리스트의 맨 끝에 추가합니다. | numbers.AddRange(new[] { 20, 30 }); // [10, 20, 30] |
| Insert(int index, T item) | 지정된 인덱스 위치에 요소를 삽입하고, 기존 요소들을 뒤로 밉니다. | numbers.Insert(1, 15); // [10, 15, 20, 30] |
2. 요소 검색 및 확인 (Search & Check)
| 메서드 | 설명 | 예시 (List<int> numbers) |
| Contains(T item) | 리스트에 특정 요소가 포함되어 있는지 확인하고, bool 값을 반환합니다. | bool has20 = numbers.Contains(20); // true |
| IndexOf(T item) | 특정 요소의 첫 번째로 발견되는 인덱스를 반환합니다. 요소가 없으면 -1을 반환합니다. | int index = numbers.IndexOf(15); // 1 |
| Count (속성) | 리스트에 포함된 요소의 개수를 반환합니다. | int count = numbers.Count; // 4 |
3. 요소 삭제 (Remove)
| 메서드 | 설명 | 예시 (List<int> numbers = [10, 15, 20, 30]) |
| Remove(T item) | 지정된 요소와 일치하는 첫 번째 항목을 찾아 삭제합니다. 성공하면 true를 반환합니다. | numbers.Remove(15); // [10, 20, 30] |
| RemoveAt(int index) | 지정된 인덱스 위치의 요소를 삭제합니다. | numbers.RemoveAt(0); // [20, 30] |
| RemoveAll(Predicate<T> match) | 지정된 **조건(Predicate)**에 맞는 모든 요소를 제거합니다. 제거된 요소의 개수를 반환합니다. | numbers.RemoveAll(x => x > 25); // 1개 제거, [20] |
| Clear() | 리스트의 모든 요소를 제거하여 빈 리스트로 만듭니다. | numbers.Clear(); // [] |
4. 기타 유용한 메서드 (Utility)
| 메서드 | 설명 | 예시 (List<int> numbers = [30, 10, 20]) |
| Sort() | 리스트의 요소들을 오름차순으로 정렬합니다. | numbers.Sort(); // [10, 20, 30] |
| Reverse() | 리스트의 요소 순서를 반대로 뒤집습니다. | numbers.Reverse(); // [20, 10, 30] |
| ToArray() | 리스트의 모든 요소를 포함하는 새로운 배열을 만듭니다. | int[] arr = numbers.ToArray(); |
| Find(Predicate<T> match) | 지정된 조건(Predicate)에 맞는 첫 번째 요소를 찾아 반환합니다. 없으면 기본값(참조 타입은 null)을 반환합니다. | int firstOdd = numbers.Find(x => x % 2 != 0); |
| FindAll(Predicate<T> match) | 지정된 조건에 맞는 모든 요소를 포함하는 새로운 리스트를 반환합니다. | List<int> evens = numbers.FindAll(x => x % 2 == 0); |
링크드 리스트 ( Linked List )
- 선형이 아닌 데이터 노드들이 메모리의 여기저기 흩어져 저장됩니다
- 노드가 앞, 뒤 노드의 주소를 기억해서 삽입 삭제가 일어나면 그 주소들만 연결시켜주면 되는 구조입니디, 리스트처럼 전체복사 안해도 됨
- 삽입/삭제가 자주 일어나느 파일 형식에 유리
- 단점은 원하는 요소를 찾기 위해서는 한번 전체적으로 주소를 타고타고 돌아줘야 찾을 수 있습니다
주요 특징 및 성능
| 연산 | 시간 복잡도 | 설명 |
| 요소 접근 (Access) | 특정 인덱스의 요소를 찾으려면 처음부터 순차적으로 노드를 따라가야 하므로 느립니다. | |
| 삽입/삭제 | 삽입/삭제 위치를 이미 알고 있다면, 노드의 주소(링크)만 변경하면 되므로 매우 빠릅니다. | |
| 중간에 삽입/삭제 | 삽입/삭제할 위치를 찾기 위해 $O(N)$이 필요하고, 실제 작업은 $O(1)$입니다. (위치 찾기 과정이 지배적) | |
| 메모리 | 비효율적 | 각 요소를 저장할 때 데이터 외에 다음 노드를 가리키는 추가적인 포인터 공간이 필요합니다. |
자주 사용하는 메서드
1. 노드 생성 및 참조
| 메서드/속성 | 설명 | 예시 (LinkedList<int> list) |
| First (속성) | 리스트의 첫 번째 노드를 반환합니다. 노드가 없으면 null을 반환합니다. | var firstNode = list.First; |
| Last (속성) | 리스트의 마지막 노드를 반환합니다. 노드가 없으면 null을 반환합니다. | var lastNode = list.Last; |
| Find(T value) | 지정된 값을 가진 첫 번째 노드를 찾아 반환합니다. 못 찾으면 null을 반환합니다. | var node = list.Find(10); |
2. 요소 삽입 (Add)
삽입 메서드는 대부분 $O(1)$의 시간 복잡도를 가집니다.
| 메서드 | 설명 | 예시 (LinkedList<int> list) |
| AddFirst(T value) | 리스트의 맨 앞에 새 노드를 삽입합니다. | list.AddFirst(10); // [10] |
| AddLast(T value) | 리스트의 맨 뒤에 새 노드를 삽입합니다. | list.AddLast(20); // [10, 20] |
| AddBefore(LinkedListNode<T> node, T value) | 지정된 노드 바로 앞에 새 노드를 삽입합니다. | var node20 = list.Find(20); list.AddBefore(node20, 15); // [10, 15, 20] |
| AddAfter(LinkedListNode<T> node, T value) | 지정된 노드 바로 뒤에 새 노드를 삽입합니다. | var node10 = list.First; list.AddAfter(node10, 12); // [10, 12, 15, 20] |
3. 요소 삭제 (Remove)
삭제 메서드 역시 대부분 $O(1)$의 시간 복잡도를 가집니다.
| 메서드 | 설명 | 예시 (LinkedList<int> list = [10, 12, 15, 20]) |
| Remove(T value) | 지정된 값을 가진 첫 번째 노드를 삭제합니다. 성공하면 true를 반환합니다. | list.Remove(12); // [10, 15, 20] |
| Remove(LinkedListNode<T> node) | 지정된 노드를 리스트에서 삭제합니다. | var node15 = list.Find(15); list.Remove(node15); // [10, 20] |
| RemoveFirst() | 리스트의 첫 번째 노드를 삭제합니다. | list.RemoveFirst(); // [20] |
| RemoveLast() | 리스트의 마지막 노드를 삭제합니다. | list.RemoveLast(); // [] |
| Clear() | 리스트의 모든 요소를 제거하여 빈 리스트로 만듭니다. | list.Clear(); |
4. 기타 속성
| 속성 | 설명 |
| Count | 리스트에 포함된 노드의 개수를 반환합니다. |
| Contains(T value) | 리스트에 특정 값이 포함되어 있는지 확인하고, bool 값을 반환합니다. (주의: 이 메서드는 전체 순회하므로 $O(N)$입니다.) |
리스트와 링크드 리스트 차이
| 특징 | 리스트 (List / 동적 배열) |
링크드 리스트 (Linked List)
|
| 데이터 저장 방식 | 연속된 메모리 공간 |
비연속적인 메모리, 노드로 연결
|
| 접근 성능 | 빠름 (O(1)) - 인덱스 사용 |
느림 (O(N)) - 순차적 탐색 필요
|
| 삽입/삭제 성능 | 느림 (O(N)) - 중간일 경우 |
빠름 (O(1)) - 링크만 변경 (위치를 알고 있다면)
|
| 메모리 오버헤드 | 적음 - 포인터 공간 불필요 |
많음 - 모든 노드에 포인터 공간 필요
|
결론적으로
- 리스트는 데이터 접근(읽기,쓰기) 하는 작업이 많고 , 삽입/삭제가 적을 때 유리
- 링크드 리스트는 데이터의 삽입/삭제 가 번번히 일어나고 접근이 덜 중요할 때 유리