[자료구조] 배열 (Array)과 연결 리스트 (Linked List) 차이

배열 (Array)

---

배열은 정적 자료구조로, 배열을 만들기 위해서는 미리 크기를 정해놓게 된다. 이렇게 정해놓으면 그 크기만큼 연속된 메모리 주소를 할당 받게 된다.

연속된 메모리 주소를 할당 받고 있기 때문에 데이터가 Index라는 것을 갖게된다. Index는 array[0] 이런 식으로 배열에 접글할 때 대괄호 안에 있는 숫자를 Index라고 한다.

Index를 갖게 된다는 것은 임의 접근이 가능하다는 장점으로 접근과 탐색에 용이하다. 하지만 크기를 미리 정해놓아서 수정하는 것은 불가능하다.

또한 이미 크기를 정해 놓았기 때무에 해당 배열 크기 이상의 데이터를 저장할 수 없다는 단점이 있다.

연결 리스트 (Linked List)

---

연결 리스트는 동적 자료구조로 크기를 정할 필요가 없다. 또한 배열처럼 연속된 메모리 주소를 할당 받지 않는다. 대신 Node가 존재하고, 그 Node안에 데이터가 있고 다음 데이터를 가리키는 주소를 가지고 있다.

연결 리스트는 위에서 말한 것처럼 크기를 정해놓지 않았기 때문에 크기 제한이 없다. 그래서 배열에 비해 데이터 추가 및 삭제가 자유로운 장점이 있다.

하지만 배열처럼 연속적인 메모리 주소를 할당 받지 않았기 떄문에 임의로 접근하는 것은 불가능하다. 즉, 데이터를 탐색할 때 순차적으로 접근해야 한다.

배열 (Array)과 연결 리스트 (Linked List) 차이

---

배열 (Array)	연결 리스트 (Linked List)
정적 자료구조	동적 자료구조
미리 크기를 정해 놓음	크기를 정할 필요 없음
연속된 메모리 주소를 할당 받음	연속된 메모리 주소를 할당받지 않음
접근, 탐색 용이	추가, 삭제 용이
Index 존재	Node 존재