이번 방학동안에는 뭔가 알 수 없이 불안불안했던 자료구조 지식들을 정리해보기로 하였다.
그 시작은 연결리스트로 해보기로 결정!
연결리스트의 개념..은 알지만 구현하라면 약간 걱정되는 것 같아서 얘부터 밟고 넘어가기로 하였다.
그럼 렛츠 디긴~👉
리스트란? 
리스트는 데이터를 선형적인 구조로 저장해 놓은 자료구조이다.
간단히 말하면 데이터를 한줄로 쭈욱 나열해서 저장해놓았다고 생각하면 된다.
위의 그림처럼 리스트는 두가지 종류로 나뉜다.
- Array List (배열)
- Linked List (연결 리스트)
Array List (배열)
배열은 논리적인 저장순서와 물리적인 저장 순서가 동일하게 저장되어있다. 즉, a-b-c 순서로 저장되어있는 배열은 실제 메모리 구조 상에서도 a-b-c 순서로 저장되어있다는 것이다.
뭐야...당연히 그런 거 아니야? 라고 생각하시는 분들은 연결 리스트의 내용도 읽어보시면 당연한 것이 아니라는 것을 알 수 있을 것이다.
Linked List (연결 리스트) 
연결 리스트는 논리적인 저장순서와 물리적인 저장 순서가 다를 수 있다.
우리가 a-b-c 순서로 데이터를 저장하였어도, 즉 논리적인 순서가 a-b-c여도, 실제 메모리 상에는 b-다른 데이터-다른데이터-a-다른 데이터-c 순으로 저장될 수 있다는 것이다.
이게..이게 어떻게 가능한데?
바로 연결리스트의 저장형태 덕분에 이러한 구조가 가능하다.
연결 리스트의 노드 구조
연결 리스트의 노드들은 위와 같이 실제 데이터를 저장하는 부분과 링크 부분으로 이루어져 있다.
여기서 핵심은 링크 부분이다.
이 링크에는 다음 노드의 "메모리 주소"가 담겨있다.
메모리 주소 : 메모리 상에서 어디에 저장되어있는지 나타내는 주소
현재 데이터에서 다음 노드를 조회하고 싶다면? 내가 저장하고 있는 다음 노드의 주소를 타고 다음 노드를 방문하면 되는 것이다.
이러한 링크 구조가 있기 때문에 아까 예시와 같이 b-다른 데이터-다른데이터-a-다른 데이터-c 형태로 저장되어 있어도, a-b-c 순서로 저장되어있구나~ 라는 것을 알 수 있는 것이다.
연결 리스트의 장단점
지금까지 리스트가 무엇인지, 배열과 연결 리스트가 어떻게 다른지 알아보았다. 그렇다면 배열과 연결 리스트 중, 어떤 상황에서 연결 리스트를 쓰는 것이 유리할까?
장점 - 데이터의 삽입, 삭제가 쉽다
바로 데이터의 삽입, 삭제가 빈번할 때 연결 리스트를 쓰는 것이 좋다.
그 이유에 대해서는 위에 설명한 배열과 연결 리스트의 저장 방식 차이를 떠올리면 이해가 쉬울 것이다.
배열
배열 같은 경우, 데이터가 물리적으로도 연속적이게 저장되어있다고 했다. 즉, a-b-c 로 저장해두면, 메모리에도 a-b-c 순서대로 다닥 다닥 붙어서 저장되어있는 것이다.
그런데 만약 내가 a와 b사이에 d를 저장하고 싶다면 어떻게 해야 할까?
일단 a와 b사이에 d가 들어갈 공간을 만들어야 한다. 이렇게 공간을 만들기 위해서는 b, c 데이터를 모두 옮겨야 한다.
그 후, 만들어진 빈 공간에 d를 삽입한다.
지금은 데이터의 개수가 a,b,c 세 가지 밖에 안되지만, 데이터가 백만개 라고 생각해보자.. 데이터 하나를 삽입하기 위해서 수십만개의 데이터가 옮겨져야 한다.
삭제의 경우도 마찬가지다.
a-d-b-c 의 배열에서 d를 다시 삭제한다고 생각해보자. d를 찾아서 지우는 것 까지는 문제가 없는데, 지우고 남은 빈 공간이 문제다. 배열은 물리적으로 연속되게 저장되어야하니까, 삽입과 마찬가지로 뒤에있는 데이터들을 옮겨 빈 공간을 채워주어야 한다.
연결리스트
그렇다면 연결 리스트는 어떨까?
삽입의 경우, 메모리 상의 어디에 저장되든 상관이 없다. 왜냐? 주소만 알면 이동할 수 있거든~ 아무데다 저장해놓고, 주소만 앞의 노드에 알려주면 된다👍굿
삭제의 경우도 큰 문제가 없다. 위와 같이 지우고 싶은 노드를 지우면서, 지울 노드의 앞 노드와 뒷 노드를 연결해주기만 하면 된다.
연결 리스트의 장점 : 삽입, 삭제가 쉽다!
단점 - 조회, 탐색에 취약
하지만, 데이터의 조회, 탐색이 빈번한 경우라면 연결리스트 대신 배열을 쓰는 것이 좋다.
이 또한 배열과 연결리스트의 저장구조의 차이때문이다.
배열
배열의 경우 메모리 상에서 연속적으로 저장되어있다. 따라서, 처음부터 끝까지 쭉 조회할 때도, 별도의 주소를 찾을 필요없이 메모리 상의 연속된 공간을 쭉 조회하면 된다.
특정 위치(인덱스)의 값을 찾을 때에도, 특정 데이터의 물리적인 주소가 시작 주소에서 얼만큼 떨어져 있는지 바로 파악할 수 있기 때문에 조회가 빠르다.
연결 리스트
그러나 연결 리스트의 경우, 다음에 저장되어 있는 데이터를 알려면, 본인의 링크에 저장되어 있는 주소를 따라가야 한다. 별도로 주소를 조회하는 과정이 필요하기 때문에, 조회와 탐색에 취약하다고 할 수 있다.
연결 리스트의 단점 : 조회, 탐색이 배열보다 느리다!
마무리
지금까지 리스트, 배열, 그리고 연결 리스트의 개념에 대해 알아보았다.
앞에서 설명했던 내용을 간단히 정리해보자.
- 리스트는 배열과 연결리스트로 나뉜다.
- 연결 리스트는 데이터와 다음 데이터의 링크를 저장하고 있다.
- 연결 리스트는 삽입, 삭제에 유리하다.
- 연결 리스트는 조회, 탐색에 취약하다.
다음 포스트에서는 위의 내용을 바탕으로 연결리스트 구현 방법에 대해 설명하겠다!
