배열(Array), 연결 리스트(Linked List)

 

- 배열 (Array) 

 

물리적 순서와 논리적 순서가 같은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음

따라서 Index로 해당 원소에 접근할 수 있다. 그렇기 때문에 원소의 Index를 알고 있으면 시간복잡도 O(1)에 해당 원소로 접근할 수 있다.

 

하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤, Shift를 해줘야 하는 상황이 발생할 수 있기 때문에 Shift하는 비용이 발생하고 이 경우의 시간 복잡도는 O(n)이 된다.

배열의 크기가 대부분 정적으로 결정된다.

 

배열은 순차적인 데이터를 저장하며 값보다는 순서가 중요하거나 다차원 데이터를 다룰 때, 어떤 특정 요소를 빠르게 읽어야할 때, 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때 사용하면 좋다.

 

 

 

 

- 연결 리스트 (Linked List) 

 

물리적 순서와 논리적 순서가 서로 다르다. 각각의 원소들은 연결 리스트 타입(단순, 이중, 원형)에 따라 자기 자신 다음(타입에 따라 이전 값의 주소값도)에 어떤 원소인지 그 해당하는 주소값을 저장한다.

연결 리스트는 동적할당을 기반으로 한 리스트이기 때문에 배열의 고정 크기의 단점과 삽입, 삭제의 속도를 보완하기 위해 만들어졌다.

 

삽입 시 연결된 노드를 끊고 새로 삽입하는 노드의 주소 값을 연결해준다.

삭제 시 해당 노드의 연결을 끊고 그 이전 노드와 다음 노드를 연결해준다.

이렇게 되면 시간 복잡도 O(1)이 된다. 

 

하지만 원하는 위치를 찾는 과정에서 첫번째 노드부터 다 확인해야되기 때문에 그 노드를 찾기 위해 시간 복잡도가 O(n)이다. 또한, 포인터를 위한 추가 메모리 공간이 필요하다.

 

 - 종류

 

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

  각 노드에 자료 공간과 한개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

 

 

2. 이중 연결 리스트 (Doubly Linked List)

  단일 연결 리스트와 비슷하지만 포인터 공간이 두 개가 있고 각각의 포인터는 이전 노드와 다음 노드를 가리킨다.

 

 

3. 원형 연결 리스트 (Circularly Linked List)

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

 

 

 

- 순환 연결리스트가 주어졌을때, 순환되는 부분 첫째 노드를 반환하는 법

Runner 기법으로 해결

 

1) FastRunner(2칸씩 이동)와 SlowRunner(1칸씩 이동)를 생성 후, Runner들을 이동시키고 루프가 있다면 언젠가 충돌한다.

 

2) 루프가 아닌 부분의 크기를 K라고 할 때, SlowRunner가 루프에 진입하기 시작하는 순간 K번 움직인 순간이고 그 순간 FastRunner는 두배를 움직이므로 LoopSize - K 만큼 떨어져 있는 위치에 도달해있을 것이다. 그렇다면 둘 사이는 현재 LoopSize - K 만큼 떨어져있을 것이다.

 

3) 직선에서는 FastRunner가 2칸 움직일 때 SlowRunner가 1칸 움직인다는 것은 한번 이동시 1만큼 멀어지지만 루프안에서는 1씩 점점 가까워진다는 것을 의미하기도 한다. 그렇다는 것은 SlowRunner가 진입 후 LoopSize - K 이후에 두 노드가 충돌한다는 의미

 

4) 두 포인터가 충돌한 지점은 루프의 시작점으로부터 LoopSize - K 만큼 떨어져 있는 곳이다. 즉 순환이 시작하는 곳에서 K만큼 떨어진 부분이라는 것이다.

 

5) 그 이후 하나의 Runner를 다시 시작점부터 출발하여 둘 다 같은 속도(1칸씩 이동)로 움직였을 때 만나는 점이 Loop의 시작점이 된다.