배열과 연결 리스트 비교

지인·2023년 8월 1일
0

CS

목록 보기
1/6

🐰 크기

배열

  • 정적 자료구조

  • 배열을 만들기 위해서는 미리 크기를 정해놔야 한다. 크기를 정해놓고 배열을 만들게 되면 딱 그 크기만큼 연속된 메모리 주소를 할당 받는다.

  • 따라서, 한번 크기를 정해 놓으면 크기 수정이 불가하고 배열 크기 이상의 데이터를 저장할 수 없다.

  • 크기를 변경하려면 새로운 배열을 생성하고 이전 배열의 데이터를 복사해야한다.

연결 리스트

  • 동적 자료구조

  • 동적으로 크기가 조절될 수 있다.

  • 그래서 요소를 추가하나 삭제할 때마다 크기가 자동으로 조절되기 때문에 크기를 직접 지정할 필요가 없다.

  • 노드가 존재하는데, 그 노드에는 저장된 데이터 값과 다음 데이터가 있는 메모리 주소(단일 연결리스트의 경우)를 가지고 있다.

  • 따라서 데이터들이 배열처럼 연속적으로 메모리에 저장되어 있지 않고 서로 떨어져 있어도 선형구조로 데이터를 저장할 수 있다.


🐰 메모리 사용

배열

  • 요소들을 연속적으로 저장하므로 메모리 상에서 효율적으로 관리된다.

  • 하지만 크기가 고정되어 있기 때문에 미리 큰 크기의 배열을 생성해야 할 수도 있다.

연결 리스트

  • 각 요소가 독립적인 노드로 구성되어 있으므로 포인터를 사용하여 연결되어 있다.

  • 이로 인해 추가적인 메모리 오버헤드가 발생할 수 있지만, 동적 크기 조절이 가능하다는 장점이 있다.


🐰 접근 시간

배열

  • 인덱스를 통해 요소에 빠르게 접근할 수 있다.

  • 인덱스를 알고있다면 O(1) 시간에 접근할 수 있다.

연결 리스트

  • 특정 요소에 접근하려면 처음부터 해당 요소까지 순차적으로 탐색해야 한다.

  • 따라서 특정 요소에 접근하는 데는 O(n) 시간이 걸린다.


🐰 추가 및 삭제 시간

배열

  • 배열의 크기가 고정되어 있기 때문에 요소를 추가하거나 삭제할 때 다른 요소들을 이동시켜야 한다.

  • 따라서 요소를 추가하거나 삭제하는 데에는 O(n) 시간이 걸린다.

연결 리스트

  • 요소를 추가하거나 삭제할 때마다 단순히 노드의 연결을 조정하면 된다.

  • 따라서 요소를 추가하거나 삭제하는 데에는 일반적으로 O(1) 시간이 걸린다. (단, 리스트 앞이나 중간에 요소를 추가/삭제하는 경우 노드를 찾는 시간이 추가적으로 필요할 수 있다.)


🐰 사용 용도

배열

  • 연속적으로 메모리를 할당받아서 데이터를 저장하기 때문에 탐색은 굉장히 빠르다. 대신에 데이터 추가, 삭제로부터 절대 자유로울 수 없다.

  • 데이터의 접근, 탐색이 중요하다면 배열을 사용

연결 리스트

  • 노드가 있기 때문에 데이터의 추가, 삭제로부터 자유로워질 수 있었지만 대신 탐색이 느려졌다.

  • 데이터의 추가, 삭제가 중요하다면 연결리스트를 사용


차이점

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

  • Array에 저장되어 있는 데이터를 조회할 때는 O(1)로 가능하지만 Linked List는 O(N)이 소요된다.

  • Array에 데이터 추가 및 삭제할 때는 O(N)이 소요되지만 Linked List는 O(1)로 가능하다.

  • 추가적으로 Array는 컴파일 과정에서 메모리가 할당되는 정적 메모리 할당인 반면 Linked List는 런타임 환경에서 메모리가 할당되는 동적 메모리 할당이다.

  • 또한 배열은 Stack 영역에 메모리 할당이 되고, Linked List는 Heap 영역에 할당이 된다.


정리

  • 배열은 정적 자료구조로, 크기를 미리 정해놓고 연속된 메모리에 요소들을 저장합니다. 이로 인해 메모리 상에서 효율적으로 관리되며, 인덱스를 통해 빠르게 요소에 접근할 수 있습니다. 또한 요소를 추가하거나 삭제할 때에는 다른 요소들을 이동시켜야 하므로 O(n) 시간이 걸립니다.
    반면, 연결 리스트는 동적 자료구조로, 동적으로 크기가 조절될 수 있습니다. 각 요소는 독립적인 노드로 구성되어 있고, 노드들은 포인터를 통해 서로 연결되어 있습니다. 요소를 추가하거나 삭제할 때에는 단순히 노드의 연결만 조정하면 되기 때문에 O(1) 시간이 걸립니다. 다만 리스트 앞이나 중간에 요소를 추가/삭제하는 경우 노드를 찾는 시간이 추가적으로 필요할 수 있습니다.
    결론적으로, 배열은 데이터의 접근, 탐색할 때 유용하고 연결 리스트는 데이터의 추가, 삭제할 때 유용하게 사용됩니다.


참고

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

배열과 연결 리스트에 대해서 알아보자!

[자료구조] Array와 Linked List의 차이는 무엇일까?

profile
열쩡

0개의 댓글