본문 바로가기
CS/자료구조

[자료구조] 배열, 링크드 리스트

by 성현0409 2023. 7. 15.

1. 배열[array]

  • 동일한 데이터 유형을 가집니다.
    • 주로 동일한 데이터 유형을 가지지만 이질형 데이터도 지원 가능한 프로그래밍 언어도 있음
    • 이질형 데이터들이 모인 집합체는 주로 레코드라고 함.
  • 실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되기 때문에 데이터에 순서가 있으며, index가 존재하여 indexing 및 slicing이 가능합니다.
    • indexing : index를 사용해 특정 요소를 리스트로 부터 읽어들이는 것
    • slicing : 요소에 특정 부분을 따로 분리해 조작하는 것

 

장점

  • 인덱스를 이용한 접근이 가능하기 때문에 모든 요소에 빠르게 접근할 수 있습니다.
  • 기록 밀도가 1이기 때문에 공간 낭비가 적습니다.
    • 리스트, 그래프 등은 데이터 외에 포인터 등 부가정보를 가지기 때문에 기록밀도가 1이 안되지만,
      배열은 부가정보 없이 데이터만 저장하기 때문에 기록밀도가 1입니다.
  • 간단하고 사용하기 쉽습니다.

 

단점

  • 배열을 선언 한 후에는 할당 된 정적 메모리 때문에 크기를 변경할 수 없습니다.
  • 중간에 특정 요소를 삽입 및 삭제하는 경우 항상 메모리가 순차적으로 이어져 있어야 하기 때문에 삽입 및 삭제된 요소로부터 위에 있는 모든 요소들을 이동시켜주어야 합니다. 그렇기 때문에 삽입 및 삭제에 비용이 많이 들게됩니다.
  • 배열의 크기가 대부분 정적으로 결정되기 때문에 삽입과 삭제가 동적으로 발생하는 상황에서 적절한 배열의 크기를 미리 결정하는 것이 어렵고, 이로 인해 오버플로나 저장공간의 낭비를 초래할 수 있습니다.

 

배열을 사용하는 경우

아래 상황에서 주로 배열을 사용합니다.

  • 순차적인 데이터를 저장하며 값보다는 순서가 중요할 때
  • 다차원 데이터를 다룰 때
  • 어떤 특정 요소를 빠르게 읽어야 할 때
  • 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때

 

2. 연결리스트(linked list)

  • 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조 
    • (포인터를 사용해서 연결된다)
  • 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성

 

왜 Linked List를 사용하나?

  • 배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한 사항이 있음
  1. 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 함
  2. 새로운 요소를 삽입하는 것은 비용이 많이 듬 (공간을 만들고, 기존 요소 전부 이동)

 

장점

  • 동적 크기
  • 삽입/삭제 용이

장점

  • 임의로 액세스를 허용할 수 없음. 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야함 (이진 검색 수행 불가능)
  • 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요

 

3. Array vs ArrayList vs LinkedList

 

  • Array는 index로 빠르게 값을 찾는 것이 가능함
  • LinkedList는 데이터의 삽입 및 삭제가 빠름
  • ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림

배열(Array)는 선언할 때 크기와 데이터 타입을 지정해야 한다. 따라서 계속 데이터가 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합하다. 또한 중간에 데이터를 삽입하거나 삭제할 때도 매우 비효율적이다. 대신, 배열을 사용하면 index가 존재하기 때문에 위치를 바로 알 수 있어 검색에 편한 장점이 있다.

 

List는 array처럼 크기를 정해주지 않아도 된다. 대신 array에서 index가 중요했다면, List에서는 순서가 중요하다.

중간에 데이터를 추가 및 삭제할 때 시간이 오래걸리는 단점이 존재한다. (더하거나 뺄때마다 줄줄이 당겨지거나 밀려날 때 진행되는 연산이 추가, 메모리도 낭비..)

 

LinkedList는?

연결리스트에는 단일, 다중 등 여러가지가 존재한다.

종류가 무엇이든, 한 노드에 연결될 노드의 포인터 위치를 가리키는 방식으로 되어있다.

데이터의 중간에 삽입 및 삭제를 하더라도 전체를 돌지 않아도 이전 값과 다음값이 가르켰던 주소값만 수정하여 연결시켜주면 되기 때문에 빠르게 진행할 수 있다.

이렇게만 보면 가장 좋은 방법 같아보이지만, List의 k번째 값을 찾아라에서는 비효율적이다.

 

array나 arrayList에서 index를 갖고 있기 때문에 검색이 빠르지만, LinkedList는 처음부터 살펴봐야하므로(순차) 검색에 있어서는 시간이 더 걸린다는 단점이 존재한다.

 

 

출처 : https://gyoogle.dev/blog/

티스토리툴바