[자료구조] Array(배열)과 Linked List(연결리스트)를 비교해보자

Array와 Linked List는 자료구조에서 갖는 형태의 개념으로 각각의 특징과 차이점을 알아보도록 하겠습니다.

 

📒 Array 개념과 특징

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

배열은 정적(static)인 자료 구조인데 그 이유는 배열을 만들기 위해서는 미리 그 크기를 정의해야하기 때문입니다.  크기를 정의하고 나면 배열 크기 이상의 데이터를 저장할 수 없다는 단점과 데이터를 순차적으로 저장하여 index를 가지게 되면서 데이터에 대한 임의 접근이 가능하다는 장점이 있습니다.

📒 Array의 시간 복잡도

• 탐색 : 인덱스를 통한 탐색은 O(1), 순차적으로 탐색시에는 O(n)
• 배열의 처음 or 중간에 삽입 및 삭제 : O(n)
• 배열의 끝에 삽입 및 삭제 : O(1)

 

---

📒 Linked List 개념과 특징

• 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫 번째 노드를 Head, 마지막 노드를 tail이라 한다.
• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
• 배열과는 다르게 메모리를 연속적으로 사용하지 않는다.
• 배열과는 다르게 순차적으로 접근해야 하는 면에서 불리할 수도 있으나, Node가 연결된 구조이기 때문에 삽입,삭제가 용이하다.
• Tree 구조의 근간이 되는 자료구조이며, Tree에서 사용될 때 그 유용성이 드러난다.

연결 리스트는 동적 자료구조라고 불립니다. 그러므로 크기를 정할 필요가 없고, 또한 배열처럼 연속된 메모리 주소를 할당 받지 않습니다.

그렇다면 순차적으로 저장되어 있지 않은 연결 리스트는 임의로 접근이 불가능한데 어떻게 접근하여 데이터를 삽입, 삭제할 수 있을까요?

 

바로 배열과는 다르게 순차적으로 데이터에 접근하여 연결 리스트의 Node라는 개념을 통해 컨트롤합니다. 노드는 저장된 데이터 값과 다음 데이터가 있는 메모리 주소(단일 연결리스트일 경우)를 가지고 있습니다. 따라서 연속적이지 않아도 선형구조로 이루어져 있어 크기의 제한 없이 데이터 추가,삭제가 가능하다는 장점을 갖고 있으며, 반대로 순차적으로 데이터에 접근해야한다는 단점을 갖고있습니다.

 

📒 Linked List의 시간 복잡도

• 탐색 : O(n)
• 연결 리스트의 처음에 삽입 및 삭제 : O(1)
• 연결 리스트의 중간에 삽입 및 삭제 : O(n)
• 연결 리스트의 끝에 삽입 및 삭제 :
  • 끝을 가리키는 별도의 포인터를 갖는 경우 : O(1)
  • 끝을 가리키는 별도의 포인터를 갖지 않는 경우 : O(n)

---

📒 Array와 Linked List 비교

	Array	Linked List
장점	인덱스를 통한 빠른 접근 가능	삽입과 삭제가 용이함
단점	삽입 및 삭제가 오래 걸림	임의 접근이 불가능하여, 순차적인 탐색진행
용도	데이터를 탐색,접근을 위한 용도에 더 적합	데이터를 삽입, 삭제를 위한 용도에 더 적합

 

 

References

https://m.blog.naver.com/raylee00/221944085465

연결리스트(Linked List)와 배열(Array), 그리고 시간복잡도의 차이에 대해

https://hongcoding.tistory.com/74

[자료구조] 배열과 연결리스트 (Array & LinkedList)

https://velog.io/@xxhaileypark/%EC%9E%90%EB%A3%8C-%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-Array-LinkedList

[자료 구조] 배열 & 연결 리스트 (Array & LinkedList)