cpu캐시 효율이 낮은것은 일반적으로 연결리스트형태를 동적할당으로 만들기때문에
각 노드간 메모리주소에 연속성이 없을 가능성이 높고
이는 캐시히트율이 낮을수 있다는 의미이기때문입니다
메모리주소의 연속성은 노드의 최대갯수가 정해져있으면 모든 노드를 미리 정적할당해서 해결할수있긴한데 노드안에 정보가 많을수록 cpu의 워드단위를 초과할수있고 연결리스트는 포인터가 반드시 필요한 구조라 노드하나의 최소크기가 큰편입니다
그래서 캐시히트율이 낮아진다고 이해해도될것같습니다
대학수준에서는 이정도만 배우고 넘어가는것같아요

nuke1115 2년 전
연결리스트 공부하면서 정리한 글입니다.
=====
이름:연결리스트/링크드리스트/Linked List
종류:선형 자료구조
1: 구조
구조는 메모리상에 비 연속적으로 노드들이 다음 또는 이전 노드를 가리키는 포인터로 연결되어있는 형태다
예를들면 a다음에 b, b다음에 c, c다음에 d... 이런형태다.
=====
2: 구성요소
연결리스트를 구성하는 요소들은 다음과 같다.
노드 => 데이터와 다음 노드를 가리키고 있는 포인터를 가지고있는 하나의 묶음이다.
구조체 또는 클레스로 구현되어있다.
데이터 => 말 그대로 데이터다
포인터 => 다음 노드의 주소를 저장중인 요소로, 노드들을 연결해주는 연결리스트의 노드와 함께 가장 중요한 요소중 하나다.
만약, 포인터가 다음 노드의 주소를 잃어버리면 그 이후 노드들에는 접근이 불가해진다. 즉 데이터가 손상된다.
노드들에도 종류가 있는데, 다음과 같다.
일반노드 => 헤드와 테일노드 둘 다 아닌 노드
헤드노드 => 연결리스트의 첫번째 노드. 일반적인 상황에서 연결리스트의 원소를 순회할때는 헤드노드를 통해서 접근을 시작한다.
테일노드 => 연결리스트의 마지막 노드. 이중 연결리스트에서는 테일노드부터 순회를 시작하기도 하며, 단일 연결리스트에서는 null이나 nullptr를 할당받게된다.
=====
3: 특징
연결리스트의 특징은 각 노드들이 메모리상에 비 연속적으로 배치되어있다는것에서 나온다.
연결리스트의 특징은 다음과 같다.
1. 각 노드들은 메모리상에 비 연속적으로 배치되어있다
=> 연결리스트는 각 노드들을 동적으로 할당한다.
동적할당된 노드들은 힙메모리의 남는공간에 할당이 되므로, 기존에 있던 노드보다 앞에 할당될수도, 뒤에 할당될수도 있다.
2. 임의접근이 불가능하다
=> 배열같이 노드들이 연속적으로 할당돼있지 않고, 힙메모리에 여기저기 흩어져있기에, 인덱스로 임의접근이 불가능하고, 무조건 노드를 전체적으로 탐색해야 특정 노드에 접근이 가능하다.
3. 탐색과정을 제외한 노드의 삽입/삭제 연산에 있어서는 효율이 상당히 좋은편이다.
=> 배열같이 연속된공간에 할당된것이 아니라 포인터로 연결되있기에, 데이터들을 뒤로 밀 필요 없이, 포인터 주소만 수정해주면 끝이다.
4. 노드 전체를 한번에 할당하는것이 아닌, 필요할때마다 추가로 개별적으로 할당하는것이 가능하다.
5. 크기가 가변적이다.
=> 노드를 새로 하나 만들고, 마지막 노드를 해당 노드로 연결해주면 크기가 확장된다. 반대로 마지막 노드를 지우면 크기가 줄어든다.
=====
4: 주요 기능들
탐색 => 어느 한 요소를 찾는다
순회 => 모든 요소를 순회한다
삽입 => 어느 한 부분에 노드를 삽입한다
삭제 => 어느 한 노드를 삭제한다
=====
5: 시간복잡도와 공간복잡도
탐색,순회 => 시간복잡도 : O(N)
삽입,삭제 => O(1) (탐색에 걸리는 시간을 제외하였을때) , O(N) (탐색에 걸리는 시간까지 포함했을때)
공간복잡도는 모두 O(1)이다.
=====
6: 종류
종류는 대표적으로 단일 연결리스트(Singly Linked List)/이중 연결리스트(Doubly Linked List)/원형 연결리스트(Circular Linked List) 가 있다.
단일 연결리스트(Singly Linked List):노드들이 오로지 다음 노드를 가리키는 포인터에 의해 연결된 형태의 연결리스트 (구성요소=> 데이터,next포인터)
이전 노드를 가리키는 포인터가 없어 개당 노드의 크기는 작은편이고, 무조건 헤드=>테일 방향으로 탐색이 진행된다.
또한, 포인터에 저장된 주소가 손상되면, 그 이후의 노드들이 유실된다는 위험성이 있다.
구현하는사람에 따라, 테일노드를 가리키는 포인터를 따로 저장해두기도 한다.
이중 연결리스트(Doubly Linked List):노드들이 자신의 다음 노드의 포인터와, 이전노드를 가리키는 포인터를 모두 가지고있는 연결리스트. (구성요소=> 데이터,next포인터, prev포인터)
노드에 이전 요소를 가리키는 포인터도 함께 가지고있어, 개당 노드의 크기가 더 크지만, 헤드=>테일/테일=>헤드 방향 모두 탐색이 가능하다.
이러한 이중 연결리스트의 특징은 탐색과 삽입/삭제에서 이점을 가져다준다.
양방향으로 순회가 가능하단점을 이용해 head와 tail에서 각각 탐색을 시작하는 형식으로 하면
,탐색속도를 단일연결리스트의 탐색속도보다 단축시킬수 있다.(알고리즘을 비효율적으로 짜면 단일연결리스트보다 느릴수도 있다)
원형 연결리스트(Circular Linked List):테일노드가 헤드노드를 가리키고있는 형태의 연결리스트.
종류는 단일,이중 연결리스트 두가지가 있는데, 테일노드는 헤드노드를(만약 이중이라면 헤드노드는 테일노드를)가리키는 순환하는 형태라는것을 빼면 똑같다.
요약:
단일 연결리스트 : 노드들이 오로지 자기의 다음 노드만 가리키고, 헤드=>테일방향 순회만 가능함
이중 연결리스트 : 노드들이 자기의 다음과 이전 노드를 가리키고, 헤드<=>테일 두가지 방향으로 순회가 가능함
원형 연결리스트 : 헤드와 테일이 연결되있는 순환하는 형태의 연결리스트. 이점을 빼면 위의 두개와 동일하다
=====
7: 장점 및 단점
장점:
1: 요소의 삭제/삽입이 간편하고 빠르다. =>포인터 몇개만 수정하면 끝
2: 크기가 동적이다.=> 연결리스트를 만들때 내가 쓸 전체 공간 크기를 지정해줄 필요가 없다.
3: 공간 이용이 효율적이다. => 연결리스트 전체가 들어갈수 있는 연속적 공간이 아닌, 노드 한개가 들어갈정도의 공간만 있으면, 거기에 할당해주고 포인터로 이어주면 된다.
단점:
1: 임의접근이 불가하다. => 무조건 순차접근만 가능.
2: 할당할 데이터만큼의 공간이 아닌, 다음 주소를 가리키는 포인터가 할당될 공간까지 추가로 할당해줘야 하기에, 요구되는 용량이 더 큰편이다.
3: 구현이 복잡하다. 잘못 구현시 메모리 누수나 메모리 참조 오류가 발생할 위험이 있다.
4: cpu캐시 효율이 낮다. (작성자가 이 부분 관련 지식이 적어서 이 부분 관련 내용은 작성하지 못할것같습니다)
=====
8:
다른 자료구조에 응용되어 사용되는 형태 : (ex. B+트리, 큐, 트리, 그래프 . . .)
LRU Cache알고리즘의 구현에 사용
해시테이블의 체이닝 구현에 사용
=====
9: 참고자료
https://www.geeksforgeeks.org/...
https://www.geeksforgeeks.org/...
https://medium.com/@nikhiltall...
https://en.wikipedia.org/wiki/...
https://s-y-130.tistory.com/23...
@gyuzic/Hashing-Chaning">https://velog.io/@gyuzic/Hashi...
============