고정 헤더 영역
상세 컨텐츠
본문
Concreate 클래스
- 인터페이스나 추상 클래스에 메소드가 구현되어있는 클래스를 Concreate 클래스라고 합니다.
- JDK 몇 가지 예로는 ArrayList, LinkedList, HashSet, HashMap이 있습니다.
ArrayList 특징
- 초기엔 고정된 배열로 할당된다.
- 데이터를 추가하는 대로 사이즈가 늘어난다.
- 배열 방이 다 차면 배열방이 2배로 늘어난다.
ArrayList 구현
public class ArrayList {
private Object[] data;
private int size;
private int index;
public ArrayList() {
this.size = 1;
this.data = new Object[this.size];
this.index = 0;
}
public void add(Object obj) {
System.out.println("index:" + this.index + ", size: " + this.size + ", data size: " + this.data.length);
if (this.index == this.size - 1) {
doubling();
}
data[this.index] = obj;
this.index++;
}
private void doubling() {
this.size = this.size * 2;
Object[] newData = new Object[this.size];
for (int i = 0; i < data.length; i++) {
newData[i] = data[i];
}
this.data = newData;
System.out.println("doubling index:" + this.index + ", size: " + this.size + ", data size: " + this.data.length);
}
public Object get(int i) throws Exception {
if (i > this.index - 1) {
throw new Exception("ArrayIndexOutOfBound");
} else if (i < 0) {
throw new Exception("Nagative Value");
}
return this.data[i];
}
public void remove(int i) throws Exception {
if (i > this.index - 1) {
throw new Exception("ArrayIndexOutOfBound");
} else if (i < 0) {
throw new Exception("Nagative Value");
}
for (int x = i; x < this.data.length - 1; x++) {
data[x] = data[x + 1];
}
this.index--;
}
}LinkedList 특징
- Collection 프레임워크의 일부이며 java.util 패키지에 소속되어있다.
- 연속된 위치에 저장되지 않고 모든 데이터가 데이터 부분과 주소 부분을 별도로 가지고 있다.
- 데이터는 포인터와 주소를 사용하여 연결한다.
- ArrayList 비교해보면 뒤로 밀리거나 채우는 작업 없이 주소만 서로 연결시켜 주면 되기 때문에 삽입, 삭제의 경우엔 빠르나 검색에 있어서는 인덱스가 없어 특정 요소에 접근하려면 순차 탐색이 필요하므로 느립니다.
class LinkedList {
private ListNode head;// ListNode 타입의 head 노드 인스턴스 변수
// LinkedList 생성자
public LinkedList() {
head = null;// head 노드 초기화
}
public void insertNode(ListNode preNode, String data) {
// 새로운 노드 생성
ListNode newNode = new ListNode(data);
// preNode.link는 preNode의 다음 노드이므로
// newNode.link = preNode.link는 새로운 노드의 link가 preNode의 다음 노드를 참조하도록 함
newNode.link = preNode.link;
// preNode의 link가 새로운 노드를 참조하도록 함.
// 최종적으로 'preNode -> newNode -> 기존 preNode의 다음 노드' 이렇게 구성됨.
preNode.link = newNode;
}
// Node 삽입 (마지막에 삽입)
public void insertNode(String data) {
// 새로운 노드 생성
ListNode newNode = new ListNode(data);
if (head == null) {
// head 노드가 null인 경우 새로운 노드 참조하도록 함.
this.head = newNode;
} else {
// head 노드가 null이 아닌 경우 temp 노드가 head 참조
// tempNode는 마지막 노드를 찾아서 참조하기 위해 사용.
ListNode tempNode = head;
// temp 노드의 link가 null이 아닐 때까지 다음 노드를 참조
// tempNode.link는 다음 노드 참조하고 있으므로,
// tempNode = tempNode.link는 tempNode 다음에 참조하도록 하는 것.
// while문 모두 실행되면 tempNode는 가장 마지막 노드를 참조하게 됨.
while (tempNode.link != null) {
// 다음 노드 참조
tempNode = tempNode.link;
}
// tempNode(마지막 노드)의 link가 다음 노드를 참조하도록 함.
tempNode.link = newNode;
}
}
// Node 삭제(중간 노드 삭제)
public void deleteNode(String data) {
// preNode는 head가 가리키는 노드를 할당
ListNode preNode = head;
// tempNode는 head가 가리키는 노드의 다음 노드. 즉, preNode의 다음 노드 할당
ListNode tempNode = head.link;
// 주어진 데이터가 preNode의 데이터와 일치하는 경우
// 즉, 첫번째 노드의 데이터와 일치하는 경우
if (data.equals(preNode.getData())) {
// head는 preNode의 다음 노드를 참조하도록 함.
head = preNode.link;
// preNode의 link는 null을 할당하여 연결을 끊음
preNode.link = null;
} else {
// tempNode가 null일 때까지 반복하여 탐색
while (tempNode != null) {
// 주어진 데이터와 temp 노드의 데이터가 일치할 경우
if (data.equals(tempNode.getData())) {
// tempNode가 마지막 노드인 경우
if (tempNode.link == null) {
preNode.link = null;
} else {
// tempNode가 마지막 모드가 아닌 경우
// preNode의 link는 tempNode의 다음 노드 참조.
// tempNodedml link는 null을 할당하여 다음 노드로의 연결을 끊음
preNode.link = tempNode.link;
tempNode.link = null;
}
break;
} else {
// 데이터가 일치하지 않은 경우
// preNode에 tempNode를 할당하고, tempNode에 다음 노드 할당.
preNode = tempNode;
tempNode = tempNode.link;
}
}
}
}
public ListNode searchNode(String data) {
ListNode tempNode = this.head;
// tempNode가 null이 아닐 때까지 반복하여 탐색
while (tempNode != null) {
if (data.equals(tempNode.getData())) {
return tempNode;
} else {
tempNode = tempNode.link;
}
}
return tempNode;
}
// 연결 리스트에 저장된 모든 데이터를 출력
public void printList() {
ListNode tempNode = this.head;
while (tempNode != null) {
System.out.println(tempNode.getData() + "");
tempNode = tempNode.link;
}
System.out.println();
}
public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
String wed = "wed";
linkedList.insertNode("sun");
linkedList.insertNode("mon");
linkedList.insertNode("tue");
linkedList.insertNode(wed);
linkedList.insertNode("thu");
linkedList.insertNode("fri");
linkedList.insertNode("sat");
linkedList.printList();
System.out.println("--------");
linkedList.deleteNode(wed);
linkedList.printList();
}참고 자료
- [자료구조 알고리즘] 자바의 ArrayList에 대해 알아보고 구현하기
