배열
리스트
vector는 Collection이전의 클래스. 속도가 비교적 느림. 또한 코테는 싱글스레드이기에 코테에서는 맞지않다.
ArrayList 와 LinkedList
ArrayList
add는 O(N)이지만 평균적으로는 O(1)이다 Capacity가 전부 찼을경우에만 O(N)인데 1.5배씩 크게 만들기 때문에 크기가 커질수록 grow가 적어진다. 더군다나 크기가 작을 때 grow는 O(상수)급이기에 크게 신경 ㄴㄴ
결론: 최악 O(N)이지만 O(1)로 여겨도 크게 문제 없다. 코테에서는 신경쓰기
import java.util.Arrays;
public class MyArrayList<E> {
private static final int DEFAULT_CAPACITY = 10;
private int size = 0;
private Object[] data;
public MyArrayList(int initialCapacity) {
data = new Object[initialCapacity];
}
public MyArrayList() {
this(DEFAULT_CAPACITY);
}
public void add(E element) {
if (size == data.length)
growCapacity();
data[size++] = element;
}
private void growCapacity() {
int newCapacity = data.length + (data.length >> 1);
data = Arrays.copyOf(data, newCapacity);
}
public E get(int idx) {
if (idx < 0 || idx >= size)
throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
return (E)data[idx];
}
public void set(int idx, E element) {
if (idx < 0 || idx >= size)
throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
data[idx] = element;
}
public void insert(int idx, E element) {
if (size == data.length) growCapacity();
int copyLength = size - idx;
System.arraycopy(data, idx, data, idx + 1, copyLength);
data[idx] = element;
size++;
}
public void remove(int idx) {
if (idx < 0 || idx >= size)
throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
int copyLength = data.length - idx - 1;
System.arraycopy(data, idx + 1, data, idx, copyLength);
size--;
}
public int size() {
return size;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
for(int i = 0; i < size; i++) {
if (i > 0) sb.append(", ");
sb.append(data[i].toString());
}
sb.append(']');
return sb.toString();
}
public static void main (String[] args) {
MyArrayList<Integer> list = new MyArrayList<>(4);
// ArrayList는 initial capacity를 지정할 수 있습니다.
// 지정하지 않는다면 default capacity만큼의 배열이 생성됩니다.
// ArrayList의 add: O(1)
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]
list.add(4); // [1, 2, 3, 4]
// 현재 capacity를 넘게되면 내부적으로 증가시킨 배열로 값을 이동합니다.
list.add(5); // [1, 2, 3, 4, 5]
// ArrayList의 특정 위치값에 대한 set: O(1)
list.set(2, -1); // [1, 2, -1, 4, 5]
// ArrayList의 위치를 지정하는 insert: O(N)
list.insert(3, 10); // [1, 2, -1, 10, 4, 5]
System.out.println(list);
for (int i = 0; i < list.size(); i++) {
// ArrayList의 특정 위치값에 대한 get: O(1)
int num = list.get(i);
System.out.printf("%d-th num: %d\n", i, num);
}
// ArrayList의 특정 위치값에 대한 remove: O(N)
list.remove(1); // [1, -1, 10, 4, 5]
int size = list.size(); // 5
System.out.printf("Size: %d, %s\n", size, list);
}
}
LinkedList
add
get
insert
remove
java.util.List
public class MySingleLinkedList<E> {
private int size = 0;
private Node<E> firstNode = null;
private Node<E> lastNode = null;
public static class Node<E> {
E item;
Node<E> next;
Node(E element, Node<E> next) {
this.item = element;
this.next = next;
}
}
public void addFirst(E element) {
Node<E> newNode = new Node<>(element, firstNode);
if (size == 0) lastNode = newNode;
firstNode = newNode;
size++;
}
public void add(E element) {
Node<E> newNode = new Node<>(element, null);
if (size == 0) firstNode = newNode;
else lastNode.next = newNode;
lastNode = newNode;
size++;
}
public Node<E> getNode(int idx) {
if (idx < 0 || idx >= size)
throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
Node<E> currentNode = firstNode;
for (int i = 0; i < idx; i++)
currentNode = currentNode.next;
return currentNode;
}
public E get(int idx) {
return getNode(idx).item;
}
public void set(int idx, E element) {
Node<E> targetNode = getNode(idx);
targetNode.item = element;
}
public void insert(Node<E> prevNode, E element) {
Node<E> newNode = new Node<>(element, prevNode.next);
prevNode.next = newNode;
if (newNode.next == null)
lastNode = newNode;
size++;
}
public void insert(int idx, E element) {
if (idx < 0 || idx > size)
throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
if (idx == 0) addFirst(element);
else if (idx == size) add((element));
else insert(getNode(idx - 1), element);
}
public void removeFirst() {
if (firstNode != null) {
firstNode = firstNode.next;
if (firstNode == null)
lastNode = null;
size--;
}
}
public void removeNext(Node<E> prevNode) {
if (prevNode.next != null) {
prevNode.next = prevNode.next.next;
if (prevNode.next == null)
lastNode = prevNode;
size--;
}
}
public void remove(int idx) {
if (idx < 0 || idx >= size)
throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
if (idx == 0) removeFirst();
else removeNext(getNode(idx - 1));
}
public Node<E> getFirstNode() {
return firstNode;
}
public Node<E> getLastNode() {
return lastNode;
}
public int size() {
return size;
}
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> currentNode = firstNode;
sb.append('[');
for(int i = 0; i < size; i++) {
if (i > 0) sb.append(", ");
sb.append(currentNode.item.toString());
currentNode = currentNode.next;
}
sb.append(']');
return sb.toString();
}
public static void main (String[] args) {
MySingleLinkedList<Integer> list = new MySingleLinkedList<>();
// LinkedList의 add: O(1)
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]
// LinkedList의 특정 위치값에 대한 add: O(N)
list.insert(0, 4); // [4, 1, 2, 3]
list.insert(3, 5); // [4, 1, 2, 5, 3]
// LinkedList의 특정 위치값에 대한 set: O(N)
list.set(2, -1); // [4, 1, -1, 5, 3]
System.out.println(list);
// LinkedList.java는 ListIterator를 사용해 순차 탐색을 지원하지만
// 이 클래스는 Node 접근자를 제공하여 직접 조작하는 형태로 사용합니다.
// ListIterator와는 달리 실제 Node를 가리킵니다.
Node<Integer> currentNode = list.getFirstNode();
// 2칸 뒤 Node로 이동 후 현재 노드 정보를 출력하는 예제입니다.
int currentIndex = 0; // index: 0, value: 4
for (int i = 0; i < 2; i++) {
currentNode = currentNode.next;
currentIndex++;
}
// index: 2, value: -1
System.out.printf("index: %d, value: %d\n", currentIndex, currentNode.item);
// LinkedList의 특정 위치값에 대한 get: O(N)
System.out.printf("index: %d, value: %d\n", 4, list.get(4));
// LinkedList의 순차 접근 중 특정 노드에 대한 remove: O(1)
list.removeNext(currentNode);
System.out.println(list); // [4, 1, -1, 3]
// LinkedList의 특정 위치값에 대한 remove: O(N)
list.remove(3); // [4, 1, -1];
int size = list.size(); // 3
System.out.printf("Size: %d, %s", size, list);
}
}
public class MyDoubleLinkedList<E> {
private int size = 0;
private Node<E> firstNode = null;
private Node<E> lastNode = null;
public static class Node<E> {
E item;
Node<E> prev;
Node<E> next;
Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.item = element;
this.next = next;
}
}
private void addFirst(E element) {
Node<E> newNode = new Node<>(null, element, firstNode);
if (size == 0) lastNode = newNode;
else firstNode.prev = newNode;
firstNode = newNode;
size++;
}
public void add(E element) {
Node<E> newNode = new Node<>(lastNode, element, null);
if (size == 0) firstNode = newNode;
else lastNode.next = newNode;
lastNode = newNode;
size++;
}
public Node<E> getNode(int idx) {
if (idx < 0 || idx >= size)
throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
Node<E> currentNode = firstNode;
for (int i = 0; i < idx; i++)
currentNode = currentNode.next;
return currentNode;
}
public E get(int idx) {
return getNode(idx).item;
}
public void set(int idx, E element) {
Node<E> targetNode = getNode(idx);
targetNode.item = element;
}
public void insert(Node<E> prevNode, E element) {
Node<E> newNode = new Node(prevNode, element, prevNode.next);
if (newNode.next != null) newNode.next.prev = newNode;
prevNode.next = newNode;
if (newNode.next == null)
lastNode = newNode;
size++;
}
public void insert(int idx, E element) {
if (idx < 0 || idx > size)
throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
if (idx == 0) addFirst(element);
else if (idx == size) add(element);
else insert(getNode(idx - 1), element);
}
public void remove(Node<E> targetNode) {
if (targetNode.prev != null)
targetNode.prev.next = targetNode.next;
else firstNode = targetNode.next;
if (targetNode.next != null)
targetNode.next.prev = targetNode.prev;
else lastNode = targetNode.prev;
targetNode.item = null;
targetNode.prev = targetNode.next = null;
size--;
}
public void remove(int idx) {
if (idx < 0 || idx >= size)
throw new IndexOutOfBoundsException("Index: " + idx + ", Size " + size);
remove(getNode(idx));
}
public Node<E> getFirstNode() {
return firstNode;
}
public Node<E> getLastNode() {
return lastNode;
}
public int size() {
return size;
}
public String toString() {
StringBuilder sb = new StringBuilder();
Node<E> currentNode = firstNode;
sb.append('[');
for(int i = 0; i < size; i++) {
if (i > 0) sb.append(", ");
sb.append(currentNode.item.toString());
currentNode = currentNode.next;
}
sb.append(']');
return sb.toString();
}
public static void main (String[] args) {
MyDoubleLinkedList<Integer> list = new MyDoubleLinkedList<>();
// LinkedList의 add: O(1)
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]
// LinkedList의 특정 위치값에 대한 add: O(N)
list.insert(0, 4); // [4, 1, 2, 3]
list.insert(3, 5); // [4, 1, 2, 5, 3]
// LinkedList의 특정 위치값에 대한 set: O(N)
list.set(2, -1); // [4, 1, -1, 5, 3]
System.out.println(list);
// LinkedList.java는 ListIterator를 사용해 순차 탐색을 지원하지만
// 이 클래스는 Node 접근자를 제공하여 직접 조작하는 형태로 사용합니다.
// ListIterator와는 달리 실제 Node를 가리킵니다.
Node<Integer> currentNode = list.getFirstNode();
// 3칸 뒤 Node로 이동 후 현재 노드 정보를 출력하는 예제입니다.
int currentIndex = 0; // index: 0, value: 4
for (int i = 0; i < 3; i++) {
currentNode = currentNode.next;
currentIndex++;
}
// index: 3, value: 5
System.out.printf("index: %d, value: %d\n", currentIndex, currentNode.item);
// 계속 같은 변수를 사용해 2칸 앞 원소로 이동 후 현재 노드 정보를 출력하는 예제입니다.
for (int i = 0; i < 2; i++) {
currentNode = currentNode.prev;
currentIndex--;
}
// index: 1, value: 1
System.out.printf("index: %d, value: %d\n", currentIndex, currentNode.item);
// LinkedList의 특정 위치값에 대한 get: O(N)
System.out.printf("index: %d, value: %d\n", 2, list.get(2));
// LinkedList의 순차 접근 중 특정 노드에 대한 remove: O(1)
list.remove(currentNode);
System.out.println(list); // [4, -1, 5, 3]
// LinkedList의 특정 위치값에 대한 remove: O(N)
list.remove(3); // [4, -1, 5];
int size = list.size(); // 3
System.out.printf("Size: %d, %s", size, list);
}
}
시간 복잡도 정리
사용 예시
ArrayList
import java.util.*;
class Main
{
public static void main (String[] args) {
List<Integer> list = new ArrayList<>(4);
// ArrayList는 initial capacity를 지정할 수 있습니다.
// 지정하지 않는다면 default capacity만큼의 배열이 생성됩니다.
// ArrayList의 add: O(1)
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]
list.add(4); // [1, 2, 3, 4]
// 현재 capacity를 넘게되면 내부적으로 증가시킨 배열로 값을 이동합니다.
list.add(5); // [1, 2, 3, 4, 5]
// ArrayList의 특정 위치값에 대한 set: O(1)
list.set(2, -1); // [1, 2, -1, 4, 5]
// ArrayList의 위치를 지정하는 add(insert): O(N)
list.add(3, 10); // [1, 2, -1, 10, 4, 5]
System.out.println(list);
for (int i = 0; i < list.size(); i++) {
// ArrayList의 특정 위치값에 대한 get: O(1)
// 특성상 Iterator보다 index접근이 자주 사용되는 편입니다.
int num = list.get(i);
System.out.printf("%d-th num: %d\n", i, num);
}
// ArrayList의 중간 원소 삭제: O(N)
list.remove(1); // [1, -1, 10, 4, 5]
int size = list.size(); // 5
System.out.printf("Size: %d\n", size);
// Collections의 sort, binarySearch 등을 사용할 수 있습니다.
Collections.sort(list);
System.out.println(list); // [-1, 1, 4, 5, 10]
}
}
LinkedList
import java.util.*;
class Main
{
public static void main (String[] args) {
List<Integer> list = new LinkedList<>();
// 굳이 다형성을 사용할 필요가 없다면 아래와 같이 인스턴스를 만들어
// LinkedList의 추가적인 메서드인 addFirst/Last 등을 사용할 수 있습니다.
// LinkedList<Integer> list = new LinkedList<>();
// LinkedList의 add: O(1)
list.add(1); // [1]
list.add(2); // [1, 2]
list.add(3); // [1, 2, 3]
list.add(4); // [1, 2, 3, 4]
// LinkedList의 위치를 지정하는 add(insert): O(N)
list.add(0, 5); // [5, 1, 2, 3, 4]
list.add(list.size(), 6); // [5, 1, 2, 3, 4, 6]
list.add(3, 7); // [5, 1, 2, 7, 3, 4, 6]
// LinkedList의 특정 위치값에 대한 set: O(N)
list.set(2, -1); // [5, 1, -1, 7, 3, 4, 6]
System.out.println(list);
// LinkedList의 특정 위치값에 대한 get: O(N)
System.out.printf("index: %d, value: %d\n", 4, list.get(4));
// LinkedList의 원소에 순차적으로 접근한다면 Iterator를 사용하는 것이 더 효율적입니다.
// ListIterator는 내부적으로 next 노드를 가리키고 있어 이를 통해 앞/뒤로 이동할 수 있습니다.
ListIterator<Integer> it = list.listIterator();
// ListIterator 생성 시 아래와 같이 [0:list.size()] 범위에서 시작 위치를 지정할 수도 있습니다.
// ListIterator<Integer> it = list.listIterator(3);
// ListIterator를 3칸 뒤로 이동 후 상태를 확인하는 예제입니다.
// 현재 Iterator: [^5, 1, -1, 7, 3, 4, 6]
for (int i = 0; i < 3; i++)
if (it.hasNext())
it.next();
// 현재 Iterator: [5, 1, -1,^ 7, 3, 4, 6]
// ListIterator의 prev/next를 확인해 생각한 위치가 맞는지 확인할 수 있습니다.
// ListIterator는 prev/next에 대한 단순 접근자를 제공하지 않기 때문에
// previous(), next()를 통해 실제 이동 후 반환 된 값을 사용해야 합니다.
int itIndex = it.nextIndex(); // 3 , [5, 1, -1,^ 7, 3, 4, 6]
int prevValue = it.previous(); // -1 , [5, 1,^ -1, 7, 3, 4, 6]
it.next(); // 원복, [5, 1, -1,^ 7, 3, 4, 6]
int nextValue = it.next(); // 7 , [5, 1, -1, 7,^ 3, 4, 6]
it.previous(); // 원복, [5, 1, -1,^ 7, 3, 4, 6]
System.out.printf("position %d iterator's prev: %d, next: %d\n", itIndex, prevValue, nextValue);
// ListIterator.set()은 iterator가 수행한 previous()와 next() 중 마지막으로 반환한 노드를 대상으로 합니다.
// 마지막으로 반환된 노드는 previous()로 반환되었던 3번 노드(7)입니다.
// LinkedList의 ListIterator를 통한 특정 노드 set: O(1)
it.set(10); // [5, 1, -1,^ 10, 3, 4, 6]
it.set(20); // [5, 1, -1,^ 20, 3, 4, 6]
System.out.println(list);
// ListIterator.remove() 역시 set()과 같이 마지막 반환되었던 노드를 대상으로 합니다.
// 여전히 마지막으로 반환된 노드는 previous()로 지나온 3번 노드(20)입니다.
// LinkedList의 ListIterator를 통한 특정 노드 remove: O(1)
it.remove(); // [5, 1, -1,^ 3, 4, 6]
// 마지막으로 반환된 노드가 삭제되었으므로 다시 previous/next로 iterator를 이동하기 전에
// it.set()이나 it.remove()를 사용하면 IllegalStateException이 발생합니다.
// it.remove(); // IllegalStateException
it.next(); // [5, 1, -1, 3,^ 4, 6]
it.next(); // [5, 1, -1, 3, 4,^ 6]
// 마지막으로 next()를 통해 4번 노드(4)을 반환했으므로 set/remove는 해당 노드를 대상으로 동작합니다.
it.remove(); // [5, 1, -1, 3,^ 6]
System.out.println(list);
// ListIterator를 통한 이동 중에 노드를 삽입하고 싶다면 add()를 사용할 수 있습니다.
// next 노드의 앞에 전달받은 값의 새로운 노드를 연결하며, 이때 set/remove를 위한 마지막 반환 노드 정보는 유실됩니다.
// LinkedList의 ListIterator를 통한 노드 삽입 insert: O(1)
it.previous(); // [5, 1, -1,^ 3, 6]
it.add(100); // [5, 1, -1,^ 100, 3, 6]
// it.remove(), it.set() // IllegalStateException
System.out.println(list);
// LinkedList의 특정 위치값에 대한 remove: O(N)
list.remove(5); // [5, 1, -1, 100, 3]
int size = list.size(); // 5
System.out.printf("Size: %d, %s\n", size, list);
// Collections의 sort, binarySearch 등을 사용할 수 있습니다.
// LinkedList의 get 복잡도로 인해 binarySearch와 같은 메서드는 비효율적일 수 있습니다.
Collections.sort(list); // [-1, 1, 3, 5, 100]
System.out.println(list);
}
}
Queue & Deque (LinkedList)
import java.util.*;
class Main
{
public static void main (String[] args) {
// FIFO 특성을 지닌 큐의 가장 기본적인 구현체인 LinkedList를 사용합니다.
Queue<Integer> q = new LinkedList<>();
// 큐의 가장 뒤에 원소 추가: O(1)
// 큐에 공간이 부족할 때 Exception이 발생하는 add와 false를 반환하는 offer가 제공됩니다.
q.offer(1); // [1]
q.offer(2); // [1, 2]
q.add(3); // [1, 2, 3]
q.add(4); // [1, 2, 3, 4]
// 큐의 가장 앞 원소 삭제: O(1)
// 큐가 비었을 때 Exception이 발생하는 remove와 null을 반환하는 poll이 제공됩니다.
q.poll(); // [2, 3, 4]
q.remove(); // [3, 4]
// 큐의 가장 앞 원소 조회: O(1)
// 큐가 비었을 때 Exception이 발생하는 element와 null을 반환하는 peek이 제공됩니다.
System.out.println(q.peek()); // 3
System.out.println(q.element()); // 3
}
}
import java.util.*;
class Main
{
public static void main (String[] args) {
Deque<Integer> q = new LinkedList<>();
// 덱의 가장 앞/뒤에 원소 추가: O(1)
// 덱에 공간이 부족할 때 Exception이 발생하는 add와 false를 반환하는 offer가 제공됩니다.
q.offerFirst(1); // [1]
q.addFirst(2); // [2, 1]
q.offerLast(3); // [2, 1, 3]
q.addLast(4); // [2, 1, 3, 4]
// 덱의 가장 앞/뒤 원소 삭제: O(1)
// 덱이 비었을 때 Exception이 발생하는 remove와 null을 반환하는 poll이 제공됩니다.
q.pollFirst(); // [1, 3, 4]
q.removeLast(); // [1, 3]
// 덱의 가장 앞/뒤 원소 조회: O(1)
// 덱이 비었을 때 Exception이 발생하는 get과 null을 반환하는 peek이 제공됩니다.
System.out.println(q.peekFirst()); // 1
System.out.println(q.getLast()); // 3
}
}
'Problem Solving > 자바 문법' 카테고리의 다른 글
그래프 이론 (0) | 2024.03.07 |
---|---|
리스트 이터레이터 (0) | 2024.03.06 |
BinarySearch중 parametric search (0) | 2024.02.27 |
자바 비트연산자 (1) | 2024.02.08 |
HashSet vs TreeSet vs LinkedHashSet (1) | 2024.02.06 |