정의 : 연속된 메모리 공간에 순차적으로 저장된 데이터의 모임 배열💡 value는 배열의 element. 즉, 요소를 뜻하고 [number]은 배열의 index를 의미
2. 특징
선형 자료구조
각 요소는 인덱스를 통해 액세스 할 수 있음
Multi-Dementional Array : 배열 안에 배열 생성 가능 = 다차원 배열
3. 장단점
장점
- 크기 변경이 어렵다 - 삭제 삽입 시, 비용이 많이 든다 - overflow가 생길 가능성이 있다 - 저장 공간이 낭비될 수 있다
단점
- 크기 변경이 어렵다 - 삭제 삽입 시, 비용이 많이 든다 - overflow가 생길 가능성이 있다 - 저장 공간이 낭비될 수 있다
4. 배열을 사용하는 경우
값보다 순서가 더 중요할 때
다차원 데이터를 사용할 때
정적인 경우. 즉, 메모리 크기가 지정된 상태에서 삭제와 삽입이 빈번하지 않을 때
5. 시간 복잡도
기능
속도
read
O(1)
insert
O(n)
delete
O(n)
search
O(n)
2. List
1. 정의
순서가 있는 데이터의 모임
2. 종류 : 단방향, 양방향, 원형
3. 특징
선형 자료구조
동적 크기를 가지는 배열
4. 장단점
장점
- 동적으로 크기를 배열할 수 있다 - 삽입과 삭제가 용이하다 - 빈틈없는 데이터의 적재가 가능 - 메모리의 재사용이 편리
단점
- 순차탐색에 불리하다(index가 중요하지 않기 때문) - 빈 element 허용 X - 검색 성능이 좋지 않음
5. 구현 방식
Array List
ArrayList<Object> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add("hello");
list.add(1,100); // list의 1 index에 100 추가
list.remove(2); //list의 2번째 데이터 삭제
list.get(3); //list의 3번째 데이터 가져오기
Iterator it = list.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
LinkedList
public void addFirst(Ojbect data){
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
size++;
if(head.next == null){
tail = head;
}
}
public void addLast(Ojbect data){
Node newNode = new Node(data);
if(size == 0){
addFirst(data);
}else{
tail.next = newNode;
tail = newNode;
size++;
}
}
public void addMidle(int node, Object data){
Node cur = head;
if(node == 0){
addFirst(data);
}else{
Node newNode = new Node(data);
while(node-- > 0){
cur = cur.next;
}
newNode.next = cur.next;
cur.next = newNode;
size++;
}
}
