[바킹독: 알고리즘] 연결 리스트

※ (링크) 바킹독 유튜브 영상을 통해

학습한 내용을 정리한 것입니다.

 

본인은 JAVA를 활용해 학습하였습니다

비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다.

 

본문의 모든 내용의 출처는 아래 명시된 링크와 같습니다.

 

 

 

[목차]  정의와 성질, 기능과 구현, STL List, 연습 문제

[실전 알고리즘] 0x04강 - 연결 리스트

출처: blog.encrypted.gg/932?category=773649

---

정의와 성질

연결 리스트는 원소를 저장할 때, 그 다음 위치를 포함하는 방식으로 저장하는 자료구조 입니다. 만약 술래를 정해준다고 하였을 때, 배열의 관점으로 접근하면 index 0번에 길동이, index 1번에 민수와 같을 것입니다. 이를 연결 리스트의 관점에서는 길동이가 민수를 기억하고, 민수가 그 다음 순서를 기억하는 것입니다.

 

연결 리스트의 성질을 보겠습니다.

 

1. 연결 리스트는 k번째 원소를 확인 및 변경하기 위해 O(k)가 필요합니다.
   
   이는 연결 리스트 구조상 어쩔 수 없습니다. 배열과 달리 공간에 연속해서 존재하는 것이 아닌, 원소가 다음 위치 정보를 갖고 있기에 처음 원소부터 k에 도달하기까지의 시간이 발생하는 것입니다.
   
   
2. 임의의 위치에 원소를 추가하거나 제거하는 것은 O(1) 입니다.
   
   이는 배열과 비교했을 때 가장 큰 차이이며, 연결 리스트의 큰 장점입니다.
   
   
3. 원소들이 메모리 상에 연속하지 않아 캐시메모리 적중률(Cache hit rate)가 낮으나, 할당이 다소 쉽습니다.
   
   

연결 리스트의 종류를 살피겠습니다.

 

1. 단일 연결 리스트 ( Singly Linked List )
   
   각 원소가 자신의 다음 원소의 주소를 갖고 있는 연결 리스트입니다.
   
   
2. 이중 연결 리스트 ( Doubly Linked List )
   
   이중 연결 리스트에서는 각 원소가 자신의 이전 원소와 다음 원소의 주소를 모두 갖고 있습니다. 단일 연결 리스트에서는 이전 주소를 알 수 없었지만, 이중 연결 리스트는 자신의 이전, 다음 주소를 알 수 있습니다.
   
   다만, 원소 정보가 하나 더 존재해 메모리를 더 사용하는 단점이 있긴 합니다.
   
   
3. 원형 연결 리스트 ( Circular Linked List )
   
   마지막 원소가 처음 원소와 연결되어 있는 것입니다. 각 원소가 이전과 다음 원소의 주소를 모두 보유하고 있어도 무관합니다.

 

면접 단골 질문

 

배열과 연결 리스트는 메모리 상 원소를 놓는 방법이 달라도 원소들 사이의 선후 관계가 1 : 1로 정의가 됩니다. 즉, 원소들 사이에서 몇 번째 원소인지 순서의 개념이 적용되는 것입니다. 그래서 배열과 연결 리스트를 선형 자료구조라고 칭합니다.

 

배열과 연결 리스트의 장점 비교!

	배열	연결 리스트
k번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가 / 제거	O(N)	O(1)
메모리 상 배치	연속	불연속
추가적으로 필요한 공간 (Overhead)	-	O(N)

 

연결 리스트는 각 원소가 이전과 다음 원소의 주소를 갖고 있어야 합니다. 32비트의 컴퓨터이면, 주소값이 32비트(=4바이트) 단위이니 4N바이트가 추가로 필요합니다. 이렇게 64bit 컴퓨터에서도 필요한 바이트를 계산할 수 있는데요. N에 비례해 시간복잡도는 O(N)이 되는 것입니다.

 

---

기능과 구현

(1) 임의의 위치에 있는 원소를 확인 / 변경, O(N)

 

임의의 위치로 가기 위해서는 첫 번째부터 순차적으로 도달해야 합니다. 이는 연결 리스트 구조상 어쩔 수 없습니다. 현재 우리는 첫 번째 원소의 주소만 알고 있습니다. 네 번째 원소의 값을 확인하고 싶다 할 때, 순차적으로 접근해 원하는 네 번째 원소에 도달할 수 있습니다.

 

그렇기에 k번째 위치 원소를 대상ㅎ으로 

 

[ 정리한거 저장 안하고 날렸음. 다시 정리하기 ;; ㅠ ]

 

---

연습문제

(1) BOJ 1406번: 에디터

 

원래 처음엔 String Builder로 접근해보았는데, 오답으로 나왔었습니다. 그래서 Stack과 Cursor 번호를 활용해 접근해보았으나, 시간초과가 발생했습니다. ( ㅠㅠ )

 

 

그래서 다른 풀이를 결국 참고해 문제를 풀었네요..또록.. 아래 풀이는 다른 분의 풀이를 보고 정리한 것입니다.

 

 

(2) 손코딩 문제 1

원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때, 해당 List의 길이를 효율적으로 구하는 방법은 무엇인가?

 

하늘 답변

--> 반복문으로 연결된 다음 주소에 접근하는 횟수를 카운트하는 것이 가장 좋을 것이라 생각됨.

 

정답

--> 동일한 노드가 나올 때까지 계속 다음 노드로 접근하면 됨. 공간복잡도 O(1), 시간복잡도 O(N)

 

(3) 손코딩 문제 2

중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때, 만나는 지점을 구하는 방법은?

 

하늘 답변

--> 반복문으로 동일한 next 값을 가지는 부분을 찾는다..?

--> Stack의 indexOf( ) 메서드를 이용해 동일한 next의 값을 가지는지 확인한다?

 

정답

--> 두 시작점 가각에 대해 끝까지 진행시켜 각각의 길이를 구함

--> 그 후, 다시 두 시작점으로 돌아와 더 긴 쪽을 둘의 차이만큼 앞으로 먼저 이동시켜놓고,

--> 두 시작점이 만날 때 까지 동시에 한 칸씩 전진시키면 됨.

--> 공간복잡도 O(1), 시간복잡도 O(A+B)

 

(4) 손코딩 문제 3

주어진 연결 리스트 안에 사이클이 존재하는지 판단하라.

 

하늘 답변

--> flag역할을 할 하나의 배열을 선언함.

--> 연결 리스트가 도달한 지점의 index 번호와 동일한 위치에 flag 배열에 체크함

--> 만약 flag 배열에 체크된 흔적이 존재한다면 반복문을 true를 반환하며 종료함

--> 만약 위 반복문에서 true를 반환하지 않고, 끝까지 실행되었다면 false 반환

 

정답

--> Floyd's cycle-finding algorithm으로, 공간복잡도 O(1)과 시간복잡도 O(N)으로 해결할 수 있음.

--> Floyd's cycle-finding algorithm이는 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발하면

--> 사이클이 있을 경우 두 커서는 반드시 만나게 됨. 

--> 반대로 사이클이 없을 경우 두 커서는 만나지 못하고 연결 리스트의 끝에 도달함.

--> 이를 이용하면 거치는 모든 노드를 저장할 필요 없이 공간복잡도 O(1)에 해결할 수 있음.

 

---

문제집

github.com/encrypted-def/basic-algo-lecture/blob/master/workbook.md

encrypted-def/basic-algo-lecture

www.acmicpc.net/workbook/view/7308

문제집: 0x04강 - 연결 리스트 (BaaaaaaaaaaarkingDog)