Array , List

배열( Array ) 

같은 타입의 여러 데이터를 하나의 묶음으로 다루는 것

배열은 생성시 설정된 셀의 수가 고정되고, 각 셀에는 인덱스 번호가 부여된다. 

( 한 번 생성된 배열은 길이를 늘리거나 줄일 수 없다. )

부여된 인덱스를 통해 해당 셀 안에 있는 데이터에 접근 할 수 있다.

 

다차원 배열

Array의 경우 연속된 메모리 공간에 할당된다.

List의 경우 불연속적으로 메모리 공간을 차지
, 다음 노드를 가리키는 주소값을 가지고 있음(포인터를 통한 접근)

 

List

순서가 있는 데이터들 모임
빈틈없는 데이터의 적재 ( 원소를 삭제했을 때 삭제된 데이터 뒤 원소로 빈틈없이 연속적으로 위치시킴 )

 

배열에서 인덱스는 유일무이한 식별자이지만, 리스트에서는 몇 번째 데이터인지 정도의 의미를 가진다.

배열과 다르게 저장공간의 크기가 고정되지 않고 가변

 

 

연결리스트( LinkedList )

LinkedList는 노드(객체) 끼리의 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조이다.
노드마다 각기 객체의 주소를 서로 참조함으로서 연결 형태를 구성하는 것이다.

데이터 집합 구조가 배열처럼 미리 공간을 할당하고 사용하는 방식이 아니라

, 데이터가 추가될 때마다 노드(객체)들이 생성되어 동적으로 추가되는 방식

 

Java의 컬렉션 프레임워크에 구현된 LinkedList 클래스는 doubly linked list로 구현 되어 있다.

단방향 연결 리스트( singly linked list )

class Node {
    Node next; // 다음 노드 주소를 저장하는 필드
    int data; // 데이터를 저장하는 필드
}

한 방향으로만 이동이 가능하다.

singly linked list에 저장된 데이터가 100개라면 99번째 데이터에 접근하려면 Node를 99번 이동해야 한다. 이를 극복한 것이 doubly linked list 구조 이다.

 

양방향 연결 리스트( doubly linked list )

class Node {
    Node next; // 다음 노드 주소
    Node prev; // 이전 노드 주소
    int data; // 데이터
}

 

단일 연결 노드 객체에서 이전 노드 주소를 담고 있는 필드 prev가 추가된 형태

역순으로도 검색이 가능, 각 요소에 대한 접근과 이동이 쉽다.

 

양방향 원형 연결 리스트( doubly circular linked list )

첫번째 노드와 마지막 노드를 각각 연결시켜 원형 처럼 만듬

 

ArrayList

배열의 상위호환 버전 정도
기존의 배열만으로는 자료를 담고 관리하는데 약간 불편함 보완

ArrayList 클래스는 내부적으로 Object[] 배열을 이용하여 요소를 저장
배열을 이용하기 때문에 인덱스를 이용해 요소에 빠르게 접근

용량(capacity)과 크기(size)에 대한 용어 차이가 모호할 수 있는데, capacity는 리스트의 공간 용량라고 보면되고, size는 현재 사용 중인 공간의 크기라  이해하면 된다.

기본 capacity는 10

크기가 고정되어있는 배열과 달리 데이터 적재량에 따라 가변적으로 공간을 늘리거나 줄인다.
배열 공간이 꽉 찰때 마다 배열을 copy하는 방식으로 늘리므로 이 과정에서 지연이 발생

 

만일 정해진 용량보다 넘게 데이터를 적재할 경우, 자체적으로 내부 배열을 큰 사이즈로 새로 만들고 기존의 배열에서 요소들을 복사함으로써, 간접적으로 리스트의 용량을 확장시키게 된다. 
배열 복사 동작 자체가 성능이 그리 좋지않아 오버헤드(Overhead)를 발생 시키게 된다.

데이터를 리스트 중간에 삽입/삭제 할 경우, 중간에 빈 공간이 생기지 않도록 요소들의 위치를 앞뒤로 자동으로 이동시키기 때문에 삽입/삭제 동작은 느리다.

 

따라서 조회를 많이 하는 경우에 사용하는 것이 좋다