[자료구조] 리스트(List)

 

 

 

자료구조,  리스트(List)에 대해 알아보기

---

 

 

 

 

 

 

 

 

List의 구조와 특징 

 

리스트란 선형 데이터를 저장하는 데이터 타입 중 하나입니다. 

 

리스트는 각 요소가 메모리 상에 연속적일 필요가 없으며, 동적으로 크기가 조정됩니다. 

 

데이터를 선형적으로 관리하지만 각 요소들이 포인터를 통해 다음 요소와 연결되기 때문에 다양한 데이터 타입의 데이터를 담을 수 있는 구조입니다. 

 

리스트는 구현 방법에 따라 순차 리스트와 연결 리스트로 나뉩니다. 

 

순차 리스트는 배열을 기반으로 구현된 리스트이고, 연결 리스트는 메모리의 동적 할당을 기반으로 구현된 리스트입니다. 

 

 

 

배열 리스트 (Array List)

 

배열 리스트는 추상적 자료형인 리스트를 배열을 사용해 구현한 것입니다. 

 

1. 장점 

• 데이터 참조 용이
• 인덱스 값을 기준으로 어디든 한 번에 참조 가능
• 인덱스로 임의 접근(Random Access)이 가능함 

 

2. 단점 

• 연속된 메모리 주소를 할당하기 때문에 배열 길이 변경 불가능 
• 삭제 시 데이터의 이동(복사)가 매우 빈번해서 비효율적임 

 

 

 

 

연결 리스트 (Linked List)

 

연결리스트는 추상적 자료형인 리스트를 구현한 것입니다. 

 

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장합니다. 

 

각 노드의 포인터는 다음 혹은 이전의 노드와의 연결을 담당합니다. 

 

 

 

 

 

 

단순 연결 리스트 (Singly Linked List)

 

단순 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고 각 노드의 포인터는 다음 노트를 가르킵니다. 

 

1. 장점 

• 노드의 수가 변동될 때 메모리를 효율적으로 사용함
• 새로운 노드의 추가 및 삭제에 용이

 

2. 단점 

• 한 방향으로만 연결 돼 있어 이전 노드로의 접근이 불가능 
• 순차적 탐색을 해야하므로 데이터 접근이 비효율적임 

 

 

 

 

원형 연결 리스트 (Circular Linked List)

 

원형 연결 리스트는 일반적인 연결 리스트의 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조입니다. 

 

1. 장점

• 어느 위치에서도 데이터를 순환적으로 접근 가능
• 동일한 데이터를 처리할 때 용이

2. 단점

• 무한 루프의 위험이 있음
• 리스트의 끝을 판별하는 로직이 추가적으로 필요함 

 

 

 

 

양방향 연결 리스트 (Doubly Linked List)

 

양방향 연결 리스트는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드 및 뒤의 노드를 가리킵니다. 

 

1. 장점 

• 데이터 검색 및 접근에 용이함 
• 주소만 조정하면 되므로 삭제에 용이함 

2. 단점

• 각 노드마다 두 개의 포인터를 저장해야 하므로 메모리 사용 과다 
• 노드 추가 및 삭제 시, 포인터를 관리하기 복잡함  

 

 

 

 

시간복잡도 알아보기 

 

1. 검색

 

배열 리스트 

 

임의 접근 방식을 사용하기 때문에 인덱스를 바로 탐색할 수 있어 탐색 시 시간 복잡도는 O(1)입니다. 

 

연결 리스트 

 

순차 접근 방식을 사용하기 때문에 탐색 시 시간복잡도는 O(n)입니다. 

 

 

 

2. 삽입

 

배열 리스트 

 

데이터가 순차적으로 저장돼 있으므로 데이터 삽입을 위해선 전부 데이터를 한 칸 씩 뒤로 옮겨야 합니다.  

 

따라서 시간 복잡도는 O(n)입니다. 

 

만약 맨 뒤에 데이터를 추가하는 경우, 다른 데이터의 위치를 옮길 필요가 없으므로 시간 복잡도는 O(1)입니다. 

 

연결 리스트

 

맨 앞에 데이터를 삽입하는 경우, 시간 복잡도는 O(1)입니다.

 

하지만 그 외의 경우에는 데이터를 위치까지 순차적으로 탐색해야 하므로 시간 복잡도는 O(n)입니다.

 

 

 

3. 삭제 

 

배열 리스트 

 

맨 뒤의 데이터를 삭제하려는 경우, 시간복잡도는 O(1)입니다.

 

하지만 그 외의 경우에는 O(n)의 시간복잡도를 갖습니다. 

 

연결 리스트

 

맨 앞의 데이터를 삭제하려는 경우, 시간복잡도는 O(1)입니다. 

 

하지만 그 외의 경우에는 O(n)의 시간복잡도를 갖습니다.

 

구분	배열 리스트	연결 리스트
임의 접근	O(1)	O(n)
삽입 (맨 뒤)	O(1)	O(1)
삽입 (임의의 위치)	O(n)	O(1)
삭제	O(n)	O(n)

 

 

 

 

결론 

배열 기반 리스트는 연결 리스트와 비교했을 때 상대적으로 데이터의 접근과 검색에 우위를 가집니다.

 

연결 리스트는 배열 리스트와 비교했을 때 상대적으로 데이터의 삽입, 삭제에 우위를 갖습니다. 

 

결론적으로, 데이터의 접근과 검색의 경우 배열 기반 리스트를 사용하고 

 

데이터의 삽입과 삭제의 경우 연결 리스트를 사용하는 것이 좋습니다.