[이론] 1. 리스트 (List) - 배열, 순차리스트, 연결리스트 (Array, Array List, Linked List)

✅ 리스트(list)란?

선형리스트라고도 하며 항목 간 순서를 정한 데이터가 나열된 자료구조. 중복이 허용된다.
구현 방법에 따라 순차리스트와 연결리스트로 구분한다.

💡 집합(set)은 순서가 없는 항목들이 나열된 구조. 중복 허용X

 

List Operation :

• insert(list, pos, item) : list의 pos 위치에 item 추가
• insert_last(list, item) : list 의 마지막 위치에 item 추가
• insert_first(list, item) : list의 첫번째 위치에 item 추가
• delete(list, pos) : list 의 pos 위치의 요소 삭제
• clear(list) : list 를 비움
• replace(list, pos, item) : list의 pos 위치의 요소를 item 으로 변경
• is-in_list(list, item) : list 에 item 이 있는지 검사
• get_entry(list, pos) : list 의 pos 위치의 요소 반환
• get_length(list) : list 의 길이 반환
• is_empty(list) : list가 비었는지 검사
• is_full(list) : list가 꽉 찼는지 검사
• print_list(list) : list의 모든 요소 표시
• merge_list(list1, list2) : 리스트 간 결합
• partition_list(list, pos) : pos 위치를 기준으로 리스트 분할

 

✅ 배열 (array)

같은 타입의 데이터를 그룹핑하여 관리하기 위한 자료구조.

index - value 쌍의 구조로, 리스트를 구현하기 위해 주로 사용된다.

 

장점

• 구현이 용이하고 추가적인 메모리 공간이 필요 없음
• index 로 element에 바로 접근하므로 탐색 속도가 빠름

 

단점

• 메모리 크기가 고정된 static 변수다. 확장이 불가능함
• 저장 또는 처리해야 하는 데이터 수가 정확하지 않으면 메모리 낭비가 발생할 수 있음
• 데이터를 삽입하고 삭제할 때마다 데이터의 이동이 발생함

 

✅ 순차리스트 (Array List)

순차적인 메모리 공간을 할당하여 구현하는 리스트. 보통 배열로 구현된다.

참고) 보통 Array 와 같은 취급을 하지만, 자바에서 Array List 라는 별도의 자료구조가 존재하므로 나누어 설명함.

 

장점

• 배열로 구현하는 경우 배열의 장점을 그대로 물려받는다.

 

단점

• 배열을 사용하는 경우 배열의 단점을 그대로 물려받는다.
• 메모리 크기가 고정되므로 확장하기 위해 별도의 처리가 필요하다.

 

💡 Array 와 Array List 의 차이

Java 에서 Array List 는 capacity 를 가지고 있어, 넣으려는 데이터가 capacity 보다 많은 경우 사이즈를 일정량 늘린다. 크기가 확장된 새로운 배열을 만들어 기존 데이터를 이동시키는 방법으로 구현되는 게 일반적. Array 와 달리 Array List 는 확장 가능하지만, Array 보다 연산속도가 느리다는 단점이 있다.

 

✅ 연결리스트 (linked list)

데이터를 불연속 공간에 흩어져 있는 상태에서 다음 데이터의 위치 정보를 보유하게 하는 구조

데이터와 다음 노드 주소를 저장할 수 있는 다른 자료구조(vector 등) 와 메모리 동적 할당 기법을 이용하여 구현함

다른 여러 자료구조(스택, 큐, 트리, 그래프)를 구현하는데도 많이 사용한다.

 

장점

• 동적으로 크기가 변할 수 있음 (확장 가능)
• 삭제나 삽입 시 위치 정보만 보유/해제하면 되므로 데이터를 이동할 필요가 없음

 

단점

• 모든 데이터가 다음 데이터의 위치를 지시하는 데 필요한 추가 메모리 공간 필요함
• 배열에 비해 구현이 복잡함
• i번째 데이터를 탐색 시 앞에서부터 순차적으로 접근하여야 함

 

✅ 단일 연결리스트 (singly linked list)

하나의 방향으로만 연결되어 있는 연결리스트

체인(chain)이라고도 함

마지막 노드의 링크는 NULL값을 가짐

 

노드 삽입 절차

1. 새로운 노드 생성하고 데이터 필드에 데이터 저장
2. 링크필드에 후행노드의 주소를 저장
3. 선행노드의 링크필드 값을 새로운 노드의 주소로 설정

 

노드 삭제 절차

1. 삭제할 노드의 데이터를 다른 곳으로 복사 (백업)
2. 삭제할 노드의 이전 노드 탐색
3. 삭제할 노드의 링크필드 값을 탐색한 선행노드의 링크필드로 설정

 

✅ 원형 연결리스트 (circular linked list)

리스트의 마지막 노드가 첫번째 노드를 가리키는 연결 리스트

즉, 마지막 노드의 링크가 NULL이 아닌 첫번째 노드임

한 노드에서 다른 모든 노드로의 접근이 가능해져 삽입, 삭제, 탐색이 용이

 

✅ 이중 연결리스트 (doubly linked list)

단순연결리스트나 원형연결리스트는 현재 노드의 바로 앞 선행 노드로 이동할 수 없음

이러한 문제점을 해결하기 위해 모든 노드는 선행노드와 후행노드 모두를 가리키는 2개의 링크필드를 갖도록 함