배열 (Array), 연결리스트 (LinkedList) 란?

배열(Array)

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

---

연결리스트 (Linked List)

• 연결 리스트는 여러개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이다.
• 첫번째 노드를 head, 마지막 노드를 tail이라고 한다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
• 배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
• Tree구조의 근간이 되는 자료구조이며, Tree에서 사용되었을 때 그 유용성도 드러난다.

---

 

# 차이점

	Array	Linked List
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	공간이 없다면 새로운 메모리를 할당해야 함.	모든 공간이 다 찼어도 맨 끝의 노드만 동적으로 추가하면 됨.
장점	인덱스를 통한 빠른 접근이 가능.	삽입/삭제 용이.
단점	삽입/삭제가 오래걸림, 데이터가 삭제되면 공간 낭비가 발생함.	임의 접근이 불가능하여 , 처음부터 탐색을 진행해야 함.

 

자료를 조회할 경우가 많다  ㅡ> Array 사용

 

삽입, 삭제가 빈번하다 ㅡ> Linked List 사용 

 

---

오늘은 알고리즘을 듣다가 배열과 연결리스트에 대해서 배웠고 이에 궁금증이 생겨 정리해 보았다.

구현을 직접 해보고 이 글에 다시 정리해야겠다.