오늘은 자료구조 중 하나인 연결리스트에 대해서 알아보기로 하자.
(많은 자료구조 중 연결리스트를 먼저 소개하는 건, 개인적으로 제일 어려웠기 때문에 ^_ㅠ... 정리를 하며 알아가고 싶어서이다....)
무슨 말인지 전혀 모르겠으므로 아래 그림을 보도록 하자.
그림을 보면 조금은 더 수월하게 이해할 수 있다.
저기 알약같이 생긴 부분이 노드 모음으로 구성된 데이터 구조이다.
앞 부분에는 값이 들어있고(10, 20, 30, 40),
뒷 부분에는 다음 노드를 가리키는 주소가 있다. (10->20, 20->30, 30->40)
그리고 이 노드 중 가장 첫 번째에 있는 것을 HEAD, 끝 부분에 있는 것을 TAIL이라 부른다.
대략적으로 연결리스트의 모양새를 알아보았으니, 다음은 종류에 대해서 알아보기로 하자.
연결리스트의 종류를 위키에서 찾아보면 꽤 많지만,
그중 다뤄보고 싶은 세 가지만 소개해보겠다.
차이점
1) 배열은 index가 있지만, 연결 리스트는 없다. 따라서 index로 접근할 수 없다. (array[index] 이런 식으로 접근이 불가능함.)
2) 배열은 메모리에 저장될 때 인접한 위치에 저장되지만, 연결 리스트는 랜덤한 위치에 저장된다.
공통점
1) 데이터들의 모음이다.
2) 선형 구조이다.
장점
삽입과 삭제할 때 일반적으로 더 빠르다.
이유 : 연결 리스트는 삽입이나 삭제될 때의 이전, 이후 노드의 참조값(next)만 변경하면 되어서. 배열의 경우, 리스트의 중간에 삽입이나 삭제를 할 경우 해당 엘리먼트의 뒤에 있는 모든 엘리먼트가 자리 이동을 해야함.
그림으로 보자면 아래와 같다.
단점
그림으로 보자면 아래와 같은 상황이다.
이와 관련해서 속도를 비교해둔 표도 있어서 첨부해보았다.
나는 이 연결리스트를 알고리즘 문제 풀이를 하면서 알게 되었고,
문제 풀이 상황에서는 연결리스트가 어떻게 나오는지 소개하면 좋겠다고 생각했다.
문제 풀이 사이트인 백준과 리트코드에서 문제를 골라보았다.
1) 연결 리스트(종합) : https://www.acmicpc.net/problemset?sort=submit_desc&solvedac_option=xz%2Cxn&algo=154&algo_if=and
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/
사실 위의 문제를 다 풀어보아도 문제에서 연결리스트를 활용하기란 쉽지 않다. (저만 그런가요?)
왕도는 없으니 꾸준히 해당 유형을 풀어보는 수밖엔 없을 것 같다. ^_ㅠ (화이팅...!)