[자료구조] Array, ArrayList, LinkedList

목차

Array & ArrayList 배열

• 같은 종류의 데이터를 저장하기 위한 자료구조

index로 배열의 요소 참조 가능

크기가 고정 → overflow 위험

직관적으로 간단함

추가/제거 시 shift 필요

삽입

public void add(int index, E x) {
		if (this.numItems >= item.length || index < 0 || index > this.numItems) {
			// 에러 처리
		} else {
			for (int i = this.numItems - 1; i >= index; i--) {
				item[i + 1] = item[i]; // index에 값을 삽입하기 위해 오른쪽으로 한 칸씩 shift
			}
			item[index] = x;
			this.numItems++;
		}
	}

제거

public E remove(int index) {
		if (isEmpty() || index > 0 || index > numItems - 1) {
			// 에러처리
			return null;
		} else {
			E tmp = item[index];
			for (int i = index; i < this.numItems; i++) {
				item[i] = item[i + 1]; // 한 칸씩 왼쪽으로 shift
			}
			numItems--;
			return tmp;
		}
	}

get / set

public E get(int index) {
		if (index >= 0 && index <= this.numItems - 1) {
			return item[index];
		} else {
			return null;
		}
	}

	public void set(int index, E x) {
		if (index >= 0 && index <= this.numItems - 1) {
			item[index] = x;
		}
	}

indexOf

public int indexOf(E x) {
		for (int i = 0; i < this.numItems; i++) {
			if (((Comparable) item[i]).compareTo(x) == 0)
				return i;
		}
		return -1;
	}

---

Linked List 연결 리스트

삽입/제거 시 shift 필요 X

값을 찾을 때, 앞에서부터 순차적으로 탐색

• 기본 구조

class Node<E> {
	public E item;
	public Node<E> next;

	public Node(E item) {
		this.item = item;
		this.next = null;
	}

	public Node(E item, Node<E> next) {

		this.item = item;
		this.next = next;
	}

}

public class MyLinkedList<E> {
	private Node<E> head;
	private int numItems;

	public MyLinkedList() {
		this.head = new Node(null);
		this.numItems = 0;
	}
}

삽입

이전의 Node가 가리키고 있던 next가 삽입 노드를 가리키게 하고, 삽입 노드의 next가 기존의 next값을 가리키게 만든다.

public void add(int index, E item) {
		Node<E> curr = this.head;
		for (int i = 0; i < index; i++) {
			curr = curr.next; // 삽입 index의 바로 전 값 찾기
		}

		Node<E> newNode = new Node<E>(item, curr.next);
		curr.next = newNode;
		numItems++;

	}

삭제

삭제할 Node의 이전 Node가 가리키고 있던 값을 삭제 Node의 next가 가리키고 있던 값으로 옮겨준다.

public void remove(int index) {
		Node<E> curr = this.head;
		for (int i = 0; i < index; i++) {
			curr = curr.next; // 삭제할 값의 바로 전 값 찾기
		}
		curr.next = curr.next.next; // 삭제할 노드의 전 노드가, 삭제할 노드의 다음 노드를 가리키게 함
		numItems--;
	}
// 에러 처리 필요

---

ArrayList와 LinkedList의 비교

	ArrayList	LinkedList
크기	고정=정적	변동=동적
공간의 연속성	O	X
정렬	빠름	느림
접근(k번째 원소)	index로 즉시 접근→빠름 Θ(1)	시작 노드부터 접근 → 느림 Θ(k)
원소 하나당 필요한 공간	적음	큼 (링크를 위한 공간 필요)
공간 낭비	충분한 크기로 선언 → 낭비O	낭비X
검색	Θ(n) (크기 순 정렬시 Θ(log n)	Θ(n)
추가/삭제	느림	빠름

 

---

참고: 쉽게 배우는 자료구조 with 자바