https://hagisilecoding.tistory.com/140
[자료구조] 리스트(unsorted & sorted list) c++ [컴공과고씨]
* 참고서적 c++ plus data structures * 전체코드는 https://github.com/goragoraki/Data-Structure 에서 볼 수 있습니다. 리스트는 배열과 같이 원소들을 저장하고 있는 것을 말합니다. 이 리스트를 두 개로 나눕니다
hagisilecoding.tistory.com
이 글을 보기 전에 위 링크를 먼저 보고 오시는게 좋습니다.
위 글 처럼 sorted 리스트의 가장 큰 문제점은 삽입과 삭제할 때 발생을 합니다.
예를 들면 1,2,3,4,6,7,8,9,10,11,12,13,14 라는 리스트가 있다고 할 때 5를 삽입한다고 한다면
배열을 이용하여 구현을 했다면 6부터 그 뒤에 있는 모든 원소들을 한 칸씩 밀어주어야 하고 삭제할 때도 마찬가지로
뒤에 모든 원소들을 앞쪽으로 땡겨야 하기 때문에 많은 오버헤드가 발생하게 됩니다.
이러한 문제점을 해결하기 위해 나온 것이 linked list라고 할 수 있습니다.
이러한 노드 타입을 여러개를 이어주는 것인데 이때 다음 노드는 next라는 곳이 가르켜 다음 노드로 이동할 수 있게 만드는 것입니다.
그림으로 표현하자면
이런식으로 되어있는 셈입니다.
그리고 중간에 노드를 삽입할 때 어떤 과정을 거치냐면
이런식으로 가르키는 곳을 변경 해주기만하면 쉽게 삽입이 가능합니다.
만약 정렬 리스트라면 앞에서 부터 이동하면서 넣으려는 값보다 큰 값이 나왔을 경우 뒤의 노드의 next를 바꾸어 주어야하기 때문에 전 노드를 가르키고 있는 포인터를 임시로 저장해 두어야 합니다.
그래서 링크드 리스트를 이용하여 비정렬 리스트 같은 경우 중간에 삽입하도록 코드를 구현할 때 배열로 구현하는 것보다 더 많은 이점을 얻을 수 있습니다. 중간의 값을 삭제 할 때도 마찬가지 입니다.
* 참고서적 c++ plus data structures
* 전체코드는 https://github.com/goragoraki/Data-Structure 에서 볼 수 있습니다.
'CS > 자료구조(Data Structure)' 카테고리의 다른 글
| [자료구조] Binary Search Tree c++ 구현 [컴공과고씨] (0) | 2023.01.26 |
|---|---|
| [자료구조] Quick sort(퀵 정렬) 구현 c++ [컴공과고씨] (0) | 2023.01.20 |
| [자료구조] Queue(큐) 구현 c++ [컴공과고씨] (0) | 2023.01.15 |
| [자료구조] Stack(스택) 구현 c++ [컴공과고씨] (0) | 2023.01.13 |
| [자료구조] 리스트(unsorted & sorted list) c++ [컴공과고씨] (0) | 2023.01.12 |