오늘은 자료구조 중 하나인 연결리스트에 대해서 알아보기로 하자.
(많은 자료구조 중 연결리스트를 먼저 소개하는 건, 개인적으로 제일 어려웠기 때문에 ^_ㅠ... 정리를 하며 알아가고 싶어서이다....)
1.1. 연결 리스트?
- 컴퓨터 과학에서 연결 리스트는 메모리의 물리적 배치에 따라 순서가 지정되지 않는 데이터 요소의 선형 모음입니다(In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory.)
- 대신, 각 요소는 다음 요소를 가리킵니다 . 그것은 함께 시퀀스를 나타내는 노드 모음으로 구성된 데이터 구조 입니다.(Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.)
무슨 말인지 전혀 모르겠으므로 아래 그림을 보도록 하자.
그림을 보면 조금은 더 수월하게 이해할 수 있다.
저기 알약같이 생긴 부분이 노드 모음으로 구성된 데이터 구조이다.
앞 부분에는 값이 들어있고(10, 20, 30, 40),
뒷 부분에는 다음 노드를 가리키는 주소가 있다. (10->20, 20->30, 30->40)
그리고 이 노드 중 가장 첫 번째에 있는 것을 HEAD, 끝 부분에 있는 것을 TAIL이라 부른다.
대략적으로 연결리스트의 모양새를 알아보았으니, 다음은 종류에 대해서 알아보기로 하자.
1.2. 연결 리스트 종류?
연결리스트의 종류를 위키에서 찾아보면 꽤 많지만,
그중 다뤄보고 싶은 세 가지만 소개해보겠다.
- 단일 연결 리스트(Singly linked list)
- 말 그대로 단방향으로만 연결된 연결리스트이다.
- 단방향이기 때문에 끝 부분에 도착했을 때(null값을 반환할 때) 다시 돌아갈 수 없다.
- 이중 연결 리스트(Doubly linked list)
- 단일 연결리스트와는 다르게 앞과 뒤에서 모두 접근이 가능한 연결리스트이다.
- 순환 연결 리스트(Circular linked list)
- 위의 연결리스트들과는 다르게 TAIL의 다음 값이 HEAD 값이다. (사실상 그래서 TAIL과 HEAD의 구분이 없다.)
2.1. 배열과의 차이점 및 공통점
-
차이점
1) 배열은 index가 있지만, 연결 리스트는 없다. 따라서 index로 접근할 수 없다. (array[index] 이런 식으로 접근이 불가능함.)
2) 배열은 메모리에 저장될 때 인접한 위치에 저장되지만, 연결 리스트는 랜덤한 위치에 저장된다.
-
공통점
1) 데이터들의 모음이다.
2) 선형 구조이다.
2.2. 배열과 비교했을 때 연결 리스트의 장점과 단점
-
장점
-
삽입과 삭제할 때 일반적으로 더 빠르다.
-
이유 : 연결 리스트는 삽입이나 삭제될 때의 이전, 이후 노드의 참조값(next)만 변경하면 되어서. 배열의 경우, 리스트의 중간에 삽입이나 삭제를 할 경우 해당 엘리먼트의 뒤에 있는 모든 엘리먼트가 자리 이동을 해야함.
-
그림으로 보자면 아래와 같다.
삽입할 때
삭제할 때
-
단점
- 검색할 때 일반적으로 더 느리다.
- 이유 : 연결 리스트의 경우, 어떤 노드를 찾으려고 할 때 무조건 head부터 검색해야 한다. 즉, 찾으려는 노드가 제일 끝 노드라면 처음부터 끝까지 리스트를 전부 순회해야 한다(단일 연결 리스트의 경우에). 반면 배열의 경우, 인덱스를 이용해서 해당 엘리먼트로 바로 접근할 수 있다.
그림으로 보자면 아래와 같은 상황이다.
이와 관련해서 속도를 비교해둔 표도 있어서 첨부해보았다.
3. 알고리즘에서 나오는 연결 리스트
나는 이 연결리스트를 알고리즘 문제 풀이를 하면서 알게 되었고,
문제 풀이 상황에서는 연결리스트가 어떻게 나오는지 소개하면 좋겠다고 생각했다.
문제 풀이 사이트인 백준과 리트코드에서 문제를 골라보았다.
1) 연결 리스트(종합) : https://www.acmicpc.net/problemset?sort=submit_desc&solvedac_option=xz%2Cxn&algo=154&algo_if=and
- 백준 대표 문제(제출 수 가장 많은 거) - 1406. 에디터 : https://www.acmicpc.net/problem/1406
2) 단일 연결 리스트 : https://leetcode.com/tag/linked-list/
-
leetcode 대표 문제(easy에서 따봉 젤 많은 거) - 21. Merge Two Sorted Lists : https://leetcode.com/problems/merge-two-sorted-lists/
-
이중 연결 리스트 : https://leetcode.com/tag/doubly-linked-list/
-
leetcode 대표 문제(medium에서 따봉 젤 많은 거) - 146. LRU Cache : https://leetcode.com/problems/lru-cache/
사실 위의 문제를 다 풀어보아도 문제에서 연결리스트를 활용하기란 쉽지 않다. (저만 그런가요?)
왕도는 없으니 꾸준히 해당 유형을 풀어보는 수밖엔 없을 것 같다. ^_ㅠ (화이팅...!)
4. 출처
