배열(Array) & 연결리스트(Linked List)

배열(Array)이란?

배열은 고정된 크기의 연속된 메모리 공간에 동일한 타입의 데이터를 저장하는 자료구조이다.

배열을 구성하는 요소

1. 배열 요소(Array Element)
   배열안에 실제 저장된 데이터 값이다.
2. 배열 인덱스(Array Index)
   배열에서 특정 요소를 참조하거나 수정할 때 사용하는 번호이다.
   
   numArr[0] = 11
   인덱스는 0, 요소는 11이다.

배열의 특징

• 데이터가 메모리에 연속된 공간에 저장된다.
• 인덱스를 이용하여 빠르게 접근 가능하다.(각 요소에 접근 시간은 모두 O(1))
• 처음 생성할 때 크기를 정해야 하며, 이후 크기 변경이 어렵다.
• 중간에 데이터를 삽입하거나 삭제할 때 데이터를 이동시켜야해서 시간이 오래걸린다.

장점

• 인덱스를 이용해 접근이 가능해 빠르게 모든 요소에 접근이 가능하다
• 공간 낭비가 적다(

단점

• 크기 변경이 어렵다
• 삽입/삭제 시 많은 데이터 이동이 발생한다.

연결리스트(Linked List)란?

연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 가지고 있는 자료구조이다.

연결 리스트를 구성하는 요소

1. 노드(Node)
   연결 리스트를 구성하는 기본 단위로, 하나의 노드는 데이터와 다음 노드를 가리키는 포인터를 가진다.
2. 링크(Link)
   노드와 노드를 연결하는 포인터를 의미한다. 링크를 통해 다음 노드로 이동할 수 있다.
   
   Node1 -> Node2 -> Node3
   Node1의 데이터는 A, Node2의 데이터는 B이라면 Node1의 포인터가 B을 가리키고 있는 구조가 된다.

연결 리스트의 특징

• 노드들은 메모리 상에서 연속적이지 않고 흩어져 있다.
• 각 노드는 자신의 다음 노드의 주소를 저장하고 있다.
• 데이터 삽입/삭제 시, 포인터만 수정하면 되기 때문에 이동이 거의 필요 없다.
• 특정 인덱스에 접근하려면 처음부터 차례대로 탐색해야 하므로 속도가 느리다(O(n)).

장점

• 크기 제한이 없고, 데이터를 추가하거나 삭제하는 것이 빠르다 (O(1), 위치를 알고 있을 때).
• 메모리를 미리 할당할 필요 없이, 필요할 때마다 동적으로 노드를 추가할 수 있다.
• 삽입/삭제할 때 기존 요소들을 밀거나 당길 필요가 없다

단점

• 임의 접근이 불가능하다. 원하는 위치로 가려면 매번 순차적으로 탐색해야 한다(O(n)).
• 노드마다 데이터를 저장하는 공간 외에 추가로 포인터를 저장할 공간이 필요하다.
• 포인터를 잘못 관리하면 메모리 누수나 단절 문제가 발생할 수 있다.

차이점 정리

항목	배열(Array)	연결 리스트(Linked List)
메모리구조	연속적	분산적
접근속도	매우 빠름(O(1))	느림 (O(n))
삽입/삭제	느림 (O(n))	빠름 (O(1)) (위치 알고 있을 때)
크기 변경	어려움 (재할당 필요)	자유로움
메모리 효율성	좋음 (추가 오버헤드 없음)	나쁨 (포인터 저장 공간 필요)
캐시 친화성	매우 좋음	나쁨