[자료구조] Array와 LinkedList란 ? 🐝

오늘은 자료구조에서 Array와 LinkedList에 대해 알아보겠습니다. 

 

배열(Array)

• 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다.
• 메모리 상에서 연속적으로 저장된다는 특징이 있기 때문에, index를 통한 접근이 용이하다.
• 배열의 크기를 처음 정하고 이후에는 변경하지 못한다.

장점

• 인덱스 접근 가능 : 인덱스를 통해 임의의 원소에 접근 가능하다. 처리하는 데이터의 양이 많아질수록 더 유리하다.
• 연속된 메모리 할당 : 주소값으로 원소에 접근할 수 있어서 편리하다.

단점

• 삽입 삭제가 어려움 : 원소를 삽입하거나 삭제할 경우, 해당 원소 이후 모든 원소를 한칸씩 밀거나 당겨야 하는 상황이 발생한다.(데이터를 연속된 메모리에 저장하기 때문이다)
• 배열의 크기는 고정적 : 처음 배열을 선언할 때 배열의 크기를 정하기 때문에 이미 만들어진 배열의 크기는 변경 불가능이다. 그렇기에 현재 배열에서 더 큰 배열을 원한다면 더 큰 크기의 배열을 선언하고 현재 배열의 값을 모두 복사해야 한다.
• 공간 낭비 발생 : 연속된 메모리를 사용하기에 중간에 데이터가 삭제되면 공간이 낭비될 수 있다. 예를 들어 배열 크기를 100으로 설정했는데 배열을 10만큼만 사용하면 나머지 90 공간을 낭비하는 셈이 된다.

언제 사용?

• 저장되는 데이터의 개수가 확실하게 정해져 있을 때
• 데이터의 삽입과 삭제가 적을 때
• 검색을 해야 할 때

연결 리스트 (Linked List)

• 연결리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 가지는 자료구조이다. 첫 번째 노드는 head, 마지막 노드를 tail이라고 한다.
• 각 노드는 현제 노드의 데이터와 다음 노드의 주소를 가지고 있다.
• 배열과 다르게 메모리를 연속적으로 사용하지 않는다.

장점

• 삽입과 삭제 용이 : 포인터로 연결되어 있어서 가리키는 노드만 변경해 주면 됨
• 크기가 가변적 : 새로운 원소를 추가할 때 동적으로 크기가 변경된다.
• 불연속적 메모리 할당 : 빈 공간 없이 데이터를 저장할 수 있다.

단점

• 인덱스 접근 불가능 : 반복자를 이용해 탐색하기 때문에 속도가 느리다.
• 포인터로 인한 공간 낭비 : 노드에는 다음 노드를 가리키는 주소까지 저장해야 하므로 불필요한 공간이 낭비된다.

언제 사용?

• 크기가 정해져 있지 않을 때
• 삽입과 삭제가 자주 일어날 때

배열과 연결 리스트 비교

 

데이터 접근이 주 업무일 경우 -> Array

데이터의 수정이 주 업무일 경우 -> Linked List

 

Array는 연속된 메모리 공간에 존재하고 Linked List는 메모리 상에 떨어져 있는 데이터들이 앞에 데이터와 뒤에 데이터를 기억하는 형태로 존재한다.

또한 Array는 stack 영역에 메모리 할당이 되고, Linked List는 Heap 영역에 할당이 된다.