우선, 글을 작성하기 전 이 글의 모든 내용은 김영한님의 JAVA 강의를 바탕으로 함을 알립니다.
💡LinkedList
이전 시간에는 ArrayList에 대해 살펴보았다. ArrayList의 단점에 대해 다시 살펴보자.
ArrayList의 단점
-
고정된 크기
ArrayList는 배열을 통해 데이터를 보관배열은 생성과 동시에 크기가 고정된 연속적인 자료구조 → 데이터의 추가/삭제 여부 예측이 어려워 메모리 낭비 발생
- 데이터의 추가/삭제 성능이 안좋다
add(추가) : 기준 index 이후의 데이터를 전부 오른쪽으로 한 칸씩 이동 후 해당 index 위치의 데이터를 새로운 것으로 대체,O(n)remove(제거) : 해당 index 위치 이후의 데이터를 전부 왼쪽으로 한 칸씩 이동,O(n)
LinkedList
LinkedList는 Node를 활용하여 낭비되는 메모리 없이 필요한 만큼만 메모리를 확보해서 사용하고, 앞 중간에 데이터를 추가하거나 삭제할 때도 효율적인 자료 구조이다.
◻️ Node
public class Node {
Object item;
Node next;
}Node는 내부에 저장할 데이터인 item과, 다음으로 연결할 노드의 참조값인 next를 가진다- 여러 노드가 연결되면 다음과 같다
◻️ 직접 구현해보는 LinkedList
제너릭과 중첩 클래스는 따로 정리 할 예정이다
public class MyLinkedListV3<E> {
private Node<E> first; // 첫번째 노드
private int size = 0; // 현재 저장되어 있는 데이터의 양
// add : 마지막에 데이터 추가
public void add(E e) {
Node<E> newNode = new Node(e);
if (first == null) {
first = newNode;
} else {
Node<E> lastNode = getLastNode(); // O(n)
lastNode.next = newNode;
}
size++;
}
private Node<E> getLastNode() {
Node<E> x = first;
while (x.next != null) { //
x = x.next;
}
return x;
}
// 특정 index 위치에 노드 add
public void add(int index, E e) {
Node<E> newNode = new Node<>(e);
if (index == 0) {
newNode.next = first;
first = newNode;
} else {
Node<E> prev = getNode(index - 1);
newNode.next = prev.next;
prev.next = newNode;
}
size ++;
}
// 특정 index의 값 변경
public E set(int index, E element) {
Node<E> x = getNode(index);
E oldValue = x.item;
x.item = element;
return oldValue;
}
// 삭제
public E remove(int index) {
Node<E> removeNode = getNode(index);
E removedItem = removeNode.item;
if (index == 0) {
first = removeNode.next;
} else {
Node<E> prev = getNode(index - 1);
prev.next = removeNode.next;
}
/**
* GC는 메모리 참조값을 기준으로 작동한다.
* GC는 더 이상 참조되지 않는 객체를 찾아 제거하기 때문에
* 제거 대상이 참조되고 있거나 다른 객체를 참조하고 있다면 GC는 이를 삭제하지 않음
* 따라서, 명시적으로 null을 통해 참조값을 제거해야한다.
*/
removeNode.item = null;
removeNode.next = null;
size--;
return removedItem;
}
// 특정 index의 value값 조회
public E get(int index) {
Node<E> node = getNode(index);
return node.item;
}
// 특정 index의 노드 조회 메서드
private Node<E> getNode(int index) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
}
public int indexOf(E o) {
int index = 0;
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
return index;
}
index++;
}
return -1;
}
public int size() {
return size;
}
@Override
public String toString() {
return "MyLinkedListV1{" +
"first=" + first +
", size=" + size +
'}';
}
// 중첩 클래스를 활용하여 Node를 LinkedList 내부에 설정
private static class Node<E> {
E item;
Node<E> next;
public Node(E item) {
this.item = item;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> x = this;
sb.append("[");
while (x != null) {
sb.append(x.item);
if (x.next != null) {
sb.append("->");
}
x = x.next;
}
sb.append("]");
return sb.toString();
}
}
}add(Object o): o를 item으로 갖는 node를 '순차적으로' 추가add(int index, Object o): index 위치에 o를 item으로 갖는 node 추가set(int index, Object o): index 위치의 노드의 item을 o로 변경get(int index): index 위치의 노드의 item 반환getNode(int index): index 위치의 노드 반환indexOf(Object o): item을 o로 갖는 노드의 인덱스 반환
ArrayList vs LinkedList
-
공통점: 중복을 허용하고 순서가 있는 자료구조 -
차이점: 성능 차이기능 ArrayList LinkedList 인덱스 조회 O(1)O(n)데이터 검색 O(n)O(n)앞에 데이터 추가 O(n)O(1)뒤에 데이터 추가 O(1)O(n)중간에 데이터 추가 O(n)O(n)
정리
- 데이터를 조회할 일이 많고, 뒷 부분에 데이터를 빈도있게 추가한다 →
ArrayList - 앞 부분에 데이터를 빈도있게 추가하거나 삭제할 일이 많다 →
LinkedList - java가 제공하는
collection의LinkedList는 이중연결리스트이기에 앞/뒤 데이터 추가 삭제 모두 성능이 좋다
JINSU