-
#1 서론
링크드 리스트에 대해 설명한다.
싱글리 링크드 리스트와 더블리 링크드 리스트의 차이점을 설명하긴 하나, 구체적인 설명은 글에 모두 담기 힘들어 생략한다.
다만 본질적인 차이점을 알려주니, 연산을 구현할때를 생각해 보면 차이점을 알 수 있을 것이다.
#2 본론
링크드 리스트 설명
링크드리스트는 배열과 다르게 RAM에 데이터를 연속적으로 저장하지 않는다. 즉, RAM에 각 데이터가 흩어져 있다는 말이다.
그럼 데이터가 흩어져 있는데, 어떻게 순서를 만들어서 리스트를 만드느냐, 그것은 바로 노드 덕분이다.
링크드 리스트는 '노드(node)'들을 연결 해서 리스트를 만든 것이다.
각 노드는 다음과 같이 구성되어있다.
구분 노드 싱글리 링크드 리스트 data 다음 노드 주소 더블리 링크드 리스트 data 이전 노드 주소 다음 노드 주소 결국 싱글리 링크드 리스트와 더블리 링크드 리스트의 차이는 각 노드에 '이전 노드 주소' 가 있냐 없냐의 차이이다.
각 노드들이 다음 노드의 주소를 가지고 있다면, 결국 순서를 지켜 리스트를 형성할 수 있게 된다.
링크드 리스트의 기본 연산 시간복잡도
그럼 이제 링크드 리스트의 추가, 탐색, 접근, 삭제 연산 등의 시간복잡도를 알아보자.
탐색, 접근은 O(n)이다.
배열과 달리 엄청난 시간이 걸린다.
왜냐하면, 특정 인덱스에 도달하려면, 첫번째 노드부터 시작해서 다음노드, 다음노드, 다음노드... 이런식으로 인덱스를 하나씩 새 주면서 탐색하고 접근해야하기 때문이다.
다음으로 맨앞, 맨뒤의 추가, 삭제 연산은 O(1)이다.
맨앞과 맨뒤에 노드를 추가 또는 삭제하려면, 그냥 원래 있던 노드의 '다음 노드 주소'만 변경해 주면 된다.
추가하려면 '다음 노드 주소'에 노드를 연결해 주면 되고,
삭제하려면 '다음 노드 주소'에 None을 저장해 주면 된다.
마지막으로 일반적인 맨앞, 맨뒤의 추가 삭제 연산은 O(n)이다.
맨앞과, 맨뒤가 아니라 링크드 리스트 중간에 추가, 삭제연산을 하려면 원하는 인덱스에 접근을 한 다음, '다음 노드 주소'를 변경해 주어야 한다.
그러므로 그냥 추가, 삭제 연산은 O(1)이지만 중간에 원하는 인덱스를 탐색하기 때문에 O(n+1)이 되어 결국 시간복잡도가 O(n)이 된다.
#3 결론
링크드 리스트는 노드를 사용하여 리스트를 만든것이다.
이로 인해 다양한 특징이 있다.
#4 참고자료
코드잇 강의
'영상, 글 요약' 카테고리의 다른 글
가장 기본적인 알고리즘, 브루트 포스(Brute Force) : 모든 경우 고려하는 알고리즘 (0) 2023.01.20 이진검색(binary search) 파이썬 반복문으로 구현 (0) 2023.01.19 정적배열, 동적배열 차이점 설명 (0) 2023.01.17 큐(Queues)와 스택(Stacks) (0) 2023.01.04 Hash Table과 array 차이점, 설명 (0) 2023.01.03