02. 배열, 연결 리스트

Data Structure & Algorithm/알고리즘(Algorithm)

02. 배열, 연결 리스트

jihyeon99 2024. 6. 10. 17:20

1. 정적 배열

연산의 종류	시간복잡도	최악의 경우 설명
삽입	O(N)	맨 앞에 값을 넣는 경우, 새로운 값이 들어갈 자리를 확보하기 위해 다른 값들이 뒤로 한칸씩 이동함
삭제	O(N)	맨 앞의 값을 삭제하는 경우, 나머지 N-1개의 값들이 모두 이동함
탐색	어떤 원소를 찾는 경우 : O(N)	처음부터 모든 값을 훑어 보며, 맨 끝에 값이 존재하는 경우
탐색	K번째 원소를 찾는 경우 : O(1)	배열은 index 기반으로 이루어져 있으므로, k-1번째 인덱스를 참조

2. 동적 배열

	정적배열	동적배열
주요 형태	int[] a = new int[100];	ArrayList<T> a = new ArrayList<>(); T는 동적 배열 안에 들어갈 원소의 타입이며, reference type만 가능 (ex. int 불가, Integer 가능)
설명	배열의 선언과 동시에 크기 정해줘야 하며, 한번 선언된 이후부터는 크기를 바꿀 수 없음	자유롭게 길이를 줄이고 늘릴 수 있으며, 메모리를 정확히 필요한 만큼만 사용
주요 연산		add(E), remove(index), size(), get(index)
주요 사용	길이에 변동 없는 경우	길이에 변동 있는 경우

정적배열과 동적배열의 삽입, 삭제, 탐색의 시간복잡도는 동일합니다.

동적 배열을 구현하기 위해서 ArrayList뿐만 아니라, Stack, Queue, Deque 등의 자료구조들을 사용할 수 있습니다.

Java에서 이런 자료구조를 사용할 수 있도록 미리 Collection을 만들어 놓았는데, 이렇게 Collection으로 정의되어 있는 자료구조를 컨테이너라고 부릅니다. 즉, ArrayList, Stack, Queue, Deque 등이 바로 컨테이너입니다. 또한 컨테이너 내에 있는 원소들을 순회하기 위해 iterator라는 이름의 반복자를 사용하기도 합니다.

Iterator<T> iterator = (기존 컨테이너 이름).iterator();

iterator.hasNext() : 그 다음 값이 더 남아 있는지를 미리 확인
iterator.next() : 위치를 이동하기 전에 현재 원소 값을 반환

ArrayList<Integer> v = new ArrayList<>();
Iterator<Integer> iterator = v.iterator();

while(iterator.hasNext()) {
    Integer num = iterator.next();
}

3. 연결 리스트

배열의 삽입과 삭제의 시간복잡도는 O(N)이므로, 삽입과 삭제를 매우 자주하는 상황이라면 비효율적입니다. 이런 문제를 해결하기 위해 '연결 리스트'라는 자료구조를 사용합니다.

	배열	연결 리스트
삽입	O(N)	O(1)	인접한 곳의 선을 끊고 연결해주는 작업만 해주면 됨
삭제	O(N)	O(1)	인접한 곳의 선을 끊고 연결해주는 작업만 해주면 됨
탐색	어떤 원소를 찾는 경우 : O(N) K번째 원소를 찾는 경우 : O(1)	O(N)	Head부터 Tail까지 일일이 확인해야
주요 사용		삽입과 삭제가 잦은 상황

연결 리스트를 구성하는 각 노드는 데이터와 다른 노드로 이동하는 경로를 가지고 있습니다.

3-1. 단일 연결 리스트 (SLL; Singly Linked List)

연결 방향이 단방향으로, 뒤로 돌아갈 수 없습니다.
리스트의 첫번째 값의 위치(head)를 반드시 명시해야, 리스트 값을 탐색할 수 있습니다.
종료지점(tail)을 명시해놓으면, 탐색할 때 추가적인 처리 없이 현재 방문한 노드가 종료 지점인지 판단하는 과정만 거쳐서 탐색을 종료할 수 있습니다.
다음 노드가 없는 경우(종료지점)에 Next에는 Null이 들어 있습니다.

set node1 = node(3)
set node2 = node(5)

// node1, node2를 연결
node1.next = node2

print(node2.data)         // 5
print(node1.next.data)    // 5

// node1, node2를 다시 분리
node1.next = null

삽입 연산
- 맨 뒤(tail 뒤)에 삽입하는 경우
  - 노드 생성 → 이어 붙이기(tail.next = new_node) → Tail 변경(tail = new_node)
- 맨 앞(head 앞)에 삽입하는 경우
  - 노드 생성 → 이어 붙이기(new_node.next = head) → Head 변경(head = new_node)
- head 바로 뒤에 삽입하는 경우
  - 노드 생성 → 이어 붙이기(new_node.next = head.next) → Head next 값 변경(head.next = new_node)

삭제 연산
- 맨 뒤(tail)를 삭제하는 경우
  - tail 바로 전 노드의 next 값을 null로 바꿈 → tail을 그 전 노드로 변경
- 맨 앞(head)을 삭제하는 경우
  - head의 값을 head.next로 변경
탐색 연산
- head부터 출발하여 tail이 나오기 전까지 계속 next를 따라가면서 탐색을 진행

3-2. 이중 연결 리스트 (DLL; Doubly Linked List)

연결 방향이 양방향으로, 앞뒤로 탐색이 가능합니다.
단일 연결 리스트에서는 한 노드에서 연결된 노드의 수가 1개인데 반해, 이중 연결 리스트는 prev가 추가된 구조로 한 노드에서 연결된 노드의 수가 2개입니다.
데이터를 삽입, 삭제할 시에는 양쪽 화살표(prev, next)를 둘 다 적절하게 변경해줘야 합니다.
null인 위치에서 next, prev, data를 조회하면 값을 참조할 수 없으므로 에러가 발생하게 됨에 유의해야 합니다.
Java에서는 List를 이용하여, 이중 연결 리스트를 사용할 수 있습니다.

- 주요형태
LinkedList<T> name = new LinkedList<>();
T는 리스트 안에 들어갈 원소의 타입이며, reference type만 가능 (ex. int 불가, Integer 가능)

- 주요 연산
addFirst(E), addLast(E), pollFirst(), pollLast(), size(), isEmpty(), peekFirst(), peekLast()

set node1 = node(5)
set node2 = node(3)

// node1, node2를 연결
node1.next = node2
node2.prev = node1

print(node1.next.data) // 결과 : 3
print(node2.next.data) // 에러 발생 (node2.next가 null이기 때문)

삽입 연산
- 맨 뒤(tail 뒤)에 삽입하는 경우
  - 노드 생성 → 이어 붙이기(new_node.prev = tail) → Tail의 next값 변경(tail.next = new_node) → Tail 변경(tail = new_node)
- 맨 앞(head 앞)에 삽입하는 경우
  - 노드 생성 → 이어 붙이기(new_node.next = head) → Head의 prev값 변경(head.prev = new_node) → Head변경(head = new_node)
삭제 연산
- 맨 뒤(tail)를 삭제하는 경우
  - tail 바로 전 노드의 next 값을 null로 변경(tail.prev.next = null) → tail을 그 전 노드로 변경(tail = tail.prev)
- 맨 앞(head)을 삭제하는 경우
  - head 바로 다음 노드의 prev 값을 null로 변경(head.next.prev = null) → head를 그 다음 노드로 변경(head = head.next)
탐색 연산
- head부터 출발하여 tail이 나오기 전까지 계속 next를 따라가면서 탐색을 진행
- tail부터 출발하여 head가 나오기 전까지 계속 prev를 따라가면서 탐색을 진행

4. Iterator

Iterator(반복자)를 이용하면 연결 리스트와 별도로 자유 자재로 값을 순회할 수 있습니다.
Iterator를 사용하는 경우 탐색의 시간복잡도 (삽입/삭제는 O(1)로 동일)
- 처음의 삽입, 삭제 연산
  - 사전에 탐색이 수반되어야 하므로
- 여러 번 동일한 위치에 삽입, 삭제를 진행
  - 이미 정의되어 있던 iterator를 유지하며, 근방에 있는 노드(앞 : interator.prev, 뒤 : iterator.next)를 삽입하고 삭제하는 것이 가능하므로 탐색에 O(1)이 소요됨

따라서, 연결리스트에서 조회, 삽입, 삭제가 위치와 밀접한 관계가 있는 경우라면, iterator를 이용하였을 때 탐색 시간을 효과적으로 줄일 수 있습니다.

처음의 삽입/삭제 연산 = O(N), 이후 동일한 위치에 삽입/삭제 연산 = O(1)

Iterator 사용 예시
- Java에서 연결 리스트를 위한 Iterator를 사용하기 위해서닌 ListIterator를 이용해야 합니다.
- .next()전에는 꼭 미리 .hasNext()를 확인하여 true일 때만 진행해야 하며, .previous()전에는 꼭 미리 .hasPrevious()를 확인하여 true일 때만 진행해야 합니다.
- .next(), .previous()는 앞 뒤로 iterator를 이동시키는 역할을 하면서 동시에 값을 반환해줍니다.
- .remove() : 직전에 it.next() / it.previous()를 진행했던 원소를 제거하고, 제거 이후 it 위치는 자동으로 변경됩니다. it.remove() 함수 실행 전에는 꼭 it.next() / it.previous()가 먼저 수행되어야 합니다.
- .add(E) : iterator it에 해당하는 위치에 새로운 원소 E를 추가합니다.

LinkedList<Integer> l = new LinkedList<>();
// 이중 연결 리스트에 'a', 'b', 'c'를 순서대로 추가합니다.
l.add('a');
l.add('b');
l.add('c');

// 1) iterator 맨 앞에서 시작
// 현재 리스트 : 'a' 'b' 'c'
ListIterator<Integer> it = l.listIterator();
if(it.hasNext())
    System.out.println(it.next());    // next는 뒤로 이동함과 동시에 값을 반환해줌 ('a')
it.remove(); // 원소 'a'를 제거합니다.
it.add('d'); // 원소 'd'를 추가합니다.

// 2) iterator 맨 뒤에서 시작
// 현재 리스트 : 'd' 'b' 'c'
it = l.listIterator(l.size());
if(it.hasPrevious())
    System.out.print(it.previous());  // previous는 앞으로 이동함과 동시에 값을 반환해줌 ('c')

연결 리스트에서는 iterator를 사용하면 처음에 해당 위치를 접근하는 데 O(N)의 시간이 소요되고 그 다음부터는 해당 위치에 접근하는데 O(1)이 소요됩니다. 따라서, 연결 리스트의 모든 원소를 출력하려면 O(N)의 시간복잡도가 소요됩니다.

하지만, iterator를 사용하지 않고 l.get(i)를 반복적으로 호출하면, 처음 해당 위치를 접근하는 데에도 O(N)의 시간이 소요되고, 그 다음에 해당 위치에 접근할때에도 O(N)이 소요됩니다. 따라서, 연결 리스트의 모든 원소를 출력하려면 O(N^2)의 시간복잡도가 소요되므로 비효율적이므로, iterator를 사용하도록 합시다.

// iterator 사용하지 않고, 연결 리스트 탐색 => O(N^2)
for(int i=0; i<l.size(); i++) {
	sb.append(it.get(i));
}

// iterator 사용하여, 연결 리스트 탐색 => O(N)
it = l.listIterator();
while(it.hasNext()) {
    sb.append(it.next());
}

5. 원형 연결 리스트 (CLL; Circular Linked List)

원형 구조의 특징은 계속 한 방향으로 움직이면 다시 출로 되돌아 온다는 것입니다.
기존 연결 리스트에서 tail와 head를 연결하여, 원형 연결 리스트를 구현할 수 있습니다.
head를 알면 바로 head.prev가 tail이 되기 때문에, 원형 연결리스트에서는 보통 head만 이용합니다.

저작자표시 (새창열림)