자료구조 배열과 리스트를 5분만에 이해하기
자료구조 배열과 리스트를 5분만에 이해하기 — #자료구조배열 #자료구조리스트 AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다. ...
#자료구조배열 #자료구조리스트
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다.
아직 자료구조 배열과 리스트에 대한 개념이 정확히 잡지는 못했습니다. 이럴때는 경험상 이런게 있구나~ 하고 넘어가는게 더 도움이 되는 부분입니다. 그러다가 직접 사용해보고 다시보면 깨닫는 부분이 더 많은 것 같습니다.
자료구조 배열과 리스트
자료구조는 프로그래머의 삶에 있어서 뼈대가 되는 지식이라고 봐도 무방할 것 같습니다. 특히나 나중에 배우게 될 알고리즘에서 자료구조를 기본적으로 알고있어야 내용을 이해하는데 어려움이 없습니다. (필자는 자료구조를 모른채 알고리즘 수업을 듣고있는데 조금 많이 버겁습니다 ㅠ.ㅠ)
배열
기차의 좌석
배열과 리스트를 설명하기 위해 기차의 좌석으로 예를 들어 보겠습니다. 예를들어 기차 A칸의 좌석이 일렬로 7개 정도 있다고 가정해봅시다. 그리고 각 좌석은 맨앞의 좌석 0번부터 맨 뒤의 좌석 6번까지 번호가 매겨져 있습니다.
여기서 우리는 A칸을 배열로 볼 수 있으며, 각 좌석 번호는 배열의 인덱스 번호로 생각해 볼 수 있습니다.
배열에 접근하기
이번에는 승무원이 각 좌석에 맞는 승객이 탔는지 확인하기 위해 좌석을 확인하는 상황을 생각해 보겠습니다. 이떄 승무원은 물론 1번부터 차례대로 확인을 하겠지만, 각각의 인덱스 번호확인은 독립적으로 이루어집니다.
조금더 쉽게 설명해 보겠습니다. 예를들어 4번 손님의 성함을 확인하는 상황이라면, 4번 좌석만 확인하면 됩니다. 나머지 좌석은 확인 할 필요가 없습니다.
이런 특징이 배열에도 나타납니다. 배열의 각 원소를 확인하기 위해선 인덱스 번호가 필요하고, 각 인덱스 번호에 해당하는 요소에 접근하는 시간은 모두 동일합니다.
배열의 크기
A칸에 대한 특징 중 하나를 짚고넘어가야 합니다. 좌석의 수를 A칸의 크기라 표현한다면, A칸의 크기는 7으로 고정되어 있습니다. 만약 승객이 2번 좌석에 없더라도 A칸의 크기는 7으로 동일합니다. 그리고 A칸은 좌석이 7개만 들어갈 수 있도록 크기를 고정시켜 두었습니다.
같은 맥락으로 배열은 크기가 고정되어 있습니다. 배열에 요소가 비게 된다면, 크기가 줄어드지 않고 메모리 공간을 낭비하게 됩니다.
배열을 추가하기
이번에는 A칸에 좌석을 하는 상황을 생각해봅시다. 앞서 A칸은 좌석을 7개만 넣을 수 있다고 말했습니다. 그래서 좌석은 A칸에 추가가 불가능하고 A칸을 확장한 A+칸을 새로만들어야합니다.
이제 A+칸을 만들었습니다. A+칸은 기존 A칸의 좌석순서를 그대로 유지하며 좌석을 배치하였습니다. 근데 추가할 좌석을 가운데로 이동시켜야 할때 문제가 발생합니다.
추가할 좌석을 가운데로 배치하기 위해서는 가운데를 비워두고 나머지 좌석들을 모두 한칸씩 뒤로 다시 시공해야합니다. (예시에서는 좌석순서는 그대로 유지해야한다는 조건이 있습니다)
이처럼 배열은 크기가 고정되어있고, 새로운 요소를 삽입하는 과정에서 매우 많은 연산이 필요로 하게됩니다. 데이터가 추가, 삭제가 빈번히 일어나는 경우에 사용하기에 좋지 못한 자료구조입니다.
배열핵심 정리
- 배열은 연속된 메모리 공간에 순차적으로 저장된 데이터의 모음입니다.(같은 데이터 타입)
- 배열은 정적 메모리로 크기를 생성시기에 정한다.
- 배열은 인덱스를 통하여 모든 요소에 동일하게 접근이 가능하다.
링크드 리스트
기차와 칸
링크드 리스트는 기차의 좌석보다는 기차자체로 비유하고 각 요소를 기차의 칸으로 생각해봅시다. 기차의 칸은 첫번째부터 마지막 칸까지 일정한 순서가 있습니다. 기차는 연결부를 통해 칸과 칸사이를 연결하고 있습니다. 고리(체인) 형태로 말이죠. 그리고 각 연결고리는 칸사이의 관계를 나타내고 있습니다.
이처럼 리스트는 노드에 요소와 포인터가 저장됩니다. 포인터는 다음 리스트 요소에 대한 정보가 담겨있습니다.
리스트에 접근하기
이제 승무원이 되어 기차 칸을 점검하는 상황이라고 생각해봅시다. 첫번째 칸부터 원하는 칸까지 이동하려면, 중간 칸을 건너뛰어 이동할 수 가 없습니다. 즉 일렬로 쭉 이어진 기차 칸사이의 관계에 따라 이동할 수 밖에 없는 것이죠.
이처럼 리스트에서 원하는 인덱스의 요소로 이동하기 위해서는 처음부터 차례대로 노드를 들여다 봐야합니다. 각 노드들에 적힌 포인터를 따라 이동해야 원하는 값에 도달할 수 있습니다.
이건 배열과 달리 처음부터 하나 하나 모든 노드를 살펴봐야 하기 때문에 접근 속도가 오래걸리는 특징이 있습니다.
리스트를 제거하기
이제 칸을 제거하는 상황을 생각해봅시다. 칸의 크기를 기차의 크기로 가정한다면, 10칸의 기차의 크기는 10입니다. 이때 기차의 칸 하나를 제거해봅시다. 그럼 칸의 갯수는 9개로 기차의 크기가 변하게 됩니다.
링크드 리스트는 배열과 달리 크기가 바뀔 수 있다는 특징이 있습니다.
리스트를 수정하기
마지막으로 칸을 중간에 추가하는 상황을 생각해봅시다. 가운데로 칸을 추가할 예정입니다.
새로운 칸을 추가하기 위해서는 가운데에 있는 연결부위를 해제 후 새로운 칸과 연결합니다. 그리고 새로운 칸은 가운데 이후에 원래 연결되어 있던 칸을 붙여넣으면 되는 겁니다.
이처럼 링크드 리스트는 리스트를 수정할때 각 포인터의 값만 바꿔주면 되기 떄문에 수정을 굉장히 효율적으로 수행할 수 있습니다.
링크드 리스트 정리
- 리스트는 동적으로 크기를 조절할 수 있다.
- 리스트는 타입이 다른 데이터를 저장할 수 있다.
- 리스트는 포인터와 참조 링크를 통해 연결되어있다.
부족한 설명이지만 가장 이해하는데 빠른 방법이 아닐까 생각이들어서 글을 작성해봅니다. 틀린 부분있다면 언제든지 지적해주세요!