JAVA 배열 & 리스트

김민혁·2021년 5월 18일

자료구조

목록 보기

1/3

같은 타입의 여러 변수를 하나의 묶음으로 다루는 것

각 저장 공간이 메모리에 연속적으로 배치되어 있다.
인덱스를 이용한 Random Access가능

→ 인덱스를 알고 있다면 특정 데이터에 접근할 때 시간복잡도는 O(1)
정적인 데이터 타입으로 한번 선언하면 배열의 사이즈를 바꿀 수 없다.
원소를 삭제하더라도 그 공간이 그대로 남는다.
- 삭제 전
- 삭제 후
  
  → 메모리 낭비
데이터를 삽입, 삭제하는 과정이 비효율적이다.

중간에 데이터를 삽입하거나 삭제하려는 경우 나머지 데이터를 전부 밀거나 당기는 작업이 추가로 필요함

데이터 탐색 시간 : O(1)

데이터 삽입 시간 : O(N)

데이터 삭제 시간 : O(N)

순서를 가진 데이터의 집합을 가리키는 추상자료형

구현 방법에 따라 크게 두 가지로 나뉜다

배열을 기반으로 구현된 리스트

메모리의 동적할당을 기반으로 구현된 리스트

내부에 데이터를 저장하는 영역을 각각 객체 생성하는 형태로 구현

→ 데이터 삽입/삭제시 효율적
데이터들의 논리적 순서와 물리적 순서가 일치하지 않고 서로의 주소를 연결함

→ Random Access불가능 + 탐색시 순차적으로 탐색해야하기 때문에 비효율적
배열과 달리 사이즈 제한 문제에서 자유로움

데이터 탐색 : O(N)

리스트의 처음 or 끝부터 순차적으로 탐색해야함
데이터 삽입 : O(1) ~ O(N)

새로운 노드를 삽입해 연결만 해주면 되기 때문에 삽입 자체는 O(1)

대신 삽입할 위치를 찾는 시간이 필요함
데이터 삭제 : O(1) ~ O(N)

삽입과 유사하게 연결을 끊기만 하면 되기 때문에 삭제 자체는 O(1)

대신 삭제할 위치를 찾는 시간 필요

한쪽 방향으로만 순회할 수 있는 리스트

class Node<T> {
	T data; // 저장할 데이터.
	Node next; // 다음 노드를 가리킴
}

양 방향으로 순회할 수 있는 리스트

자바의 LinkedList는 이 방식으로 구현되어있다

class Node<T> {
	T data; // 저장할 데이터
	Node prev; // 이전 노드를 가리킴
	Node next; // 다음 노드를 가리킴
}