Data Structure (자료구조)

비전공자는 도전해볼 수 있고, 전공자는 쉽게 배울 수 있는 데이터 스트럭쳐 수업

ArrayList - Java 구현

자바에 내장된 ArrayList는 꽤나 복잡합니다. 현실의 문제를 반영하기 위해서 여러가지 고려가 되어 있기 때문이죠. 따라서 자바에 내장된 ArrayList의 소스코드는 학습용으로 적합하지 않습니다. 우리 수업에서는 리스트라는 개념을 프로그래밍적으로 구현하기 위한 최소한의 것에 집중하겠습니다.

전체 코드는 본 문서의 제일 아래에 있습니다.

객체생성

우선 ArrayList라는 이름의 객체를 만들겠습니다.

ArrayList.java 

package list.arraylist.implementation;

public class ArrayList {
    private int size = 0;
	private Object[] elementData = new Object[100];
}

Main.java 

package list.arraylist.implementation;

public class Main {

    public static void main(String[] args) {
		
		ArrayList numbers = new ArrayList();

	}

}

데이터의 추가

마지막 위치에 추가

데이터를 마지막 위치에 추가하는 메소드의 구현은 아래와 같습니다.

public boolean addLast(Object element) {
	elementData[size] = element;
	size++;
	return true;
}

Main.java에서 위의 메소드를 사용해봅시다.

public static void main(String[] args) {
	ArrayList numbers = new ArrayList();
	numbers.addLast(10);
	numbers.addLast(20);
	numbers.addLast(30);
	numbers.addLast(40);
}

중간에 추가

데이터를 중간에 추가하는 로직은 조금 더 복잡합니다. 데이터를 추가할 빈공간을 확보해야 하기 때문입니다. 전체 코드를 봅시다.

public boolean add(int index, Object element) {
	// 엘리먼트 중간에 데이터를 추가하기 위해서는 끝의 엘리먼트부터 index의 노드까지 뒤로 한칸씩 이동시켜야 합니다.
	for (int i = size - 1; i >= index; i--) {
		elementData[i + 1] = elementData[i];
	}
	// index에 노드를 추가합니다.
	elementData[index] = element;
	// 엘리먼트의 숫자를 1 증가 시킵니다.
	size++;
	return true;
}

엘리먼트의 이동을 코드로 표현하는 것이 처음에는 쉽지 않습니다. 아래 그림을 봅시다.

그림에 표시된 숫자의 순서대로 엘리먼트를 왼쪽에서 오른찍으로 옮겨야 합니다. 이 때 가장 중요한 것은 반복조건을 헷갈리지 않는 것입니다. 반복문을 만들 때는 시작과 끝을 잘 파악하는 것이 중요합니다.

  • 시작 : 반복작업이 시작되는 인덱스로 이 값은 size-1로 구할 수 있습니다.
  • 끝 : 반복작업이 끝나는 엘리먼트의 인덱스는 메소드 add의 첫번째 인자의 값을 사용하면 됩니다.
  • 반복작업 : 감소연산 i--

이 작업을 통해서 엘리먼트를 한칸씩 뒤로 이동시킬 수 있습니다. 빈자리에 엘리먼트를 삽입합니다.

 엘리먼트의 이동이 끝나면 아래와 같이 elementData에 element를 추가합니다.

elementData[index] = element;

엘리먼트를 추가 했기 때문에 size의 값을 1 증가시킵니다.

size++;

지금까지 엘리먼트를 추가시키는 방법에 대해서 알아봤습니다.

Main.java

ArrayList numbers = new ArrayList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
numbers.addLast(40);
numbers.add(1, 15);

처음에 추가

데이터를 끝에 추가하는 메소드의 구현은 아래와 같습니다.

public boolean addFirst(Object element){
	return add(0, element);
}

Main.java

ArrayList numbers = new ArrayList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
numbers.addLast(40);
numbers.add(1, 15);
numbers.addFirst(5);

데이터 확인

데이터를 확인하기 위해서 toString 객체를 상속해서 구현하겠습니다.

public String toString(){
	String str = "[";
	for(int i=0; i < size; i++){
		str += elementData[i];
		if(i < size-1){
			str += ",";
		}
	}
	return str + "]";
}

이제 Main.java에서 아래와 같이 실행하면 리스트의 엘리먼트를 쉽게 파악할 수 있습니다.

public static void main(String[] args) {
	ArrayList numbers = new ArrayList();
	numbers.addLast(10);
	numbers.addLast(20);
	numbers.addLast(30);
	numbers.addLast(40);
	numbers.add(1, 15);
	numbers.addFirst(5);
	System.out.println(numbers);
}

출력값

[5,10,15,20,30,40]

삭제

데이터를 삭제하는 것은 중간에 추가하는 것과 유사합니다.

public Object remove(int index) {
	// 엘리먼트를 삭제하기 전에 삭제할 데이터를 removed 변수에 저장합니다.
	Object removed = elementData[index];
	// 삭제된 엘리먼트 다음 엘리먼트부터 마지막 엘리먼트까지 순차적으로 이동해서 빈자리를 채웁니다.
	for (int i = index + 1; i <= size - 1; i++) {
		elementData[i - 1] = elementData[i];
	}
	// 크기를 줄입니다.
	size--;
	// 마지막 위치의 엘리먼트를 명시적으로 삭제해줍니다. 
	elementData[size] = null;
	return removed;
}

그림에 나타난 것처럼 엘리먼트를 삭제할 때는 뒤에 있는 엘리먼트를 한칸씩 전진시킵니다. 이 때 시작과 끝을 잘 파악하는 것이 중요합니다.

엘리먼트를 옮기는 작업이 끝난 후에는 size의 값을 1 감소시킵니다.

size--;

Main.java

ArrayList numbers = new ArrayList();
numbers.addLast(10);
numbers.addLast(15);
numbers.addLast(20);
numbers.addLast(30);
numbers.remove(1);
System.out.println(numbers);
[10,20,30]

처음과 끝의 엘리먼트 삭제

public Object removeFirst(){
	return remove(0);
}

public Object removeLast(){
	return remove(size-1);
}

 Main.java

ArrayList numbers = new ArrayList();
numbers.addLast(5);
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
numbers.addLast(40);
numbers.removeFirst();
numbers.removeLast();
System.out.println(numbers);
[10,20,30]

데이터 가져오기

데이터를 가져오는 기능은 get입니다. get은 인자로 전달된 인덱스 값을 그대로 배열로 전달합니다. 배열은 메모리의 주소에 직접 접근하는 랜덤 엑세스(random access)이기 때문에 매우 빠르게 처리 됩니다.

public Object get(int index) {
	return elementData[index];
}
ArrayList numbers = new ArrayList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
numbers.addLast(40);
System.out.println(numbers.get(0));
System.out.println(numbers.get(1));
System.out.println(numbers.get(2));
10
20
30

엘리먼트의 크기

엘리먼트의 크기를 알아내는 법은 간단합니다. 내부적으로 size라는 값을 유지하고 있기 때문에 이 값을 돌려주기만 하면 됩니다.

public int size() {
    return size;
}

Main.java

ArrayList numbers = new ArrayList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
System.out.println(numbers.size());
3

탐색

특정한 값을 가진 엘리먼트의 인덱스 값을 알아내는 방법을 알아봅시다. 값이 있다면 그 값이 발견되는 첫번째 인덱스 값을 리턴하고 값이 없다면 -1을 리턴 합니다.

public Object indexOf(Object o){
    for(int i=0; i < size; i++){
		if(o.equals(elementData[i])){
			return i;
		}
	}
	return -1;
}
ArrayList numbers = new ArrayList();
numbers.addLast(10);
numbers.addLast(20);
numbers.addLast(30);
System.out.println(numbers.indexOf(20));
System.out.println(numbers.indexOf(40)); 

1
-1

반복

이제부터 반복 작업을 알아보겠습니다. ArrayList의 엘리먼트를 순회하는 방법은 아래와 같이 하면 됩니다.

for(int i=0; i<numbers.size(); i++){
	System.out.println(numbers.get(i));
}

위와 같은 방법으로 반복을 사용하셔도 됩니다. 하지만 아래와 같이 사용하는 것이 더 좋은 방법입니다. 이것이 왜 더 좋은 방법인지는 LinkedList와 비교가 필요하기 때문에 LinkedList에서 살펴보기로 하고 일단은 다른 방법도 알아봅시다.

ArrayList.ListIterator it = numbers.listIterator();
while (it.hasNext()) {
	int value = (int) it.next();
	System.out.println(value);
}

위의 코드는 ListIterator라는 객체를 이용한 방법입니다. ListIterator 객체는 반복작업을 위해서 고안된 것인데요. 이 객체를 만드는 방법은 ArrayList의 listIterator 메소드를 호출하는 것입니다. 우선 이 메소드를 만드는 코드를 봅시다.

public ListIterator listIterator() {
	// ListIterator 인스턴스를 생성해서 리턴합니다.
	return new ListIterator();
}

아래는 ListIterator 클래스입니다.

public class ListIterator {
	// 현재 탐색하고 있는 순서를 가르키는 인덱스 값
	private int nextIndex = 0;

	// next 메소르를 호출할 수 있는지를 체크합니다.
	public boolean hasNext() {
		// nextIndex가 엘리먼트의 숫자보다 적다면 next를 이용해서 탐색할 엘리먼트가 존재하는 것이기 때문에 true를 리턴합니다. 
		return nextIndex < size();
	}
	
	// 순차적으로 엘리먼트를 탐색해서 리턴합니다. 
	public Object next() {
		// nextIndex에 해당하는 엘리먼트를 리턴하고 nextIndex의 값을 1 증가 시킵니다.
		return elementData[nextIndex++];
	}
}
// previous 메소드를 호출해도 되는지를 체크합니다.
public boolean hasPrevious(){
	// nextIndex가 0보다 크다면 이전 엘리먼트가 존재한다는 의미입니다.
	return nextIndex > 0;
}

// 순차적으로 이전 노드를 리턴합니다.
public Object previous(){
	// 이전 엘리먼트를 리턴하고 nextIndex의 값을 1감소합니다. 
	return elementData[--nextIndex];
}



// 현재 엘리먼트를 추가합니다. 
public void add(Object element){
	ArrayList.this.add(nextIndex++, element);
}

// 현재 엘리먼트를 삭제합니다. 
public void remove(){
	ArrayList.this.remove(nextIndex-1);
	nextIndex--;
}

 전체코드

 ArrayList.java 

package list.arraylist.implementation;

public class ArrayList {
    private int size = 0;
	private Object[] elementData = new Object[100];

	public ArrayList() {

	}
	
	public boolean addLast(Object element) {
	    elementData[size] = element;
	    size++;
	    return true;
	}
	
	public boolean add(int index, Object element) {
		// 엘리먼트 중간에 데이터를 추가하기 위해서는 끝의 엘리먼트부터 index의 노드까지 뒤로 한칸씩 이동시켜야 합니다.
		for (int i = size - 1; i >= index; i--) {
			elementData[i + 1] = elementData[i];
		}
		// index에 노드를 추가합니다.
		elementData[index] = element;
		// 엘리먼트의 숫자를 1 증가 시킵니다.
		size++;
		return true;
	}
	
	public boolean addFirst(Object element){
		return add(0, element);
	}

	public String toString() {
		String str = "[";
		for (int i = 0; i < size; i++) {
			str += elementData[i];
			if (i < size - 1)
				str += ",";
		}
		return str + "]";
	}
	
	public Object remove(int index) {
		// 엘리먼트를 삭제하기 전에 삭제할 데이터를 removed 변수에 저장합니다.
		Object removed = elementData[index];
		// 삭제된 엘리먼트 다음 엘리먼트부터 마지막 엘리먼트까지 순차적으로 이동해서 빈자리를 채웁니다.
		for (int i = index + 1; i <= size - 1; i++) {
			elementData[i - 1] = elementData[i];
		}
		// 크기를 줄입니다.
		size--;
		// 마지막 위치의 엘리먼트를 명시적으로 삭제해줍니다. 
		elementData[size] = null;
		return removed;
	}	
	
	public Object removeFirst(){
		return remove(0);
	}

	public Object removeLast(){
		return remove(size-1);
	}

	public Object get(int index) {
		return elementData[index];
	}

	public int size() {
		return size;
	}

	public int indexOf(Object o) {
		for (int i = 0; i < size; i++) {
			if (o.equals(elementData[i])) {
				return i;
			}
		}
		return -1;
	}

	public ListIterator listIterator() {
		// ListIterator 인스턴스를 생성해서 리턴합니다.
		return new ListIterator();
	}

	

	class ListIterator {
		// 현재 탐색하고 있는 순서를 가르키는 인덱스 값
		private int nextIndex = 0;

		// next 메소르를 호출할 수 있는지를 체크합니다.
		public boolean hasNext() {
			// nextIndex가 엘리먼트의 숫자보다 적다면 next를 이용해서 탐색할 엘리먼트가 존재하는 것이기 때문에 true를 리턴합니다. 
			return nextIndex < size();
		}
		
		// 순차적으로 엘리먼트를 탐색해서 리턴합니다. 
		public Object next() {
			// nextIndex에 해당하는 엘리먼트를 리턴하고 nextIndex의 값을 1 증가 시킵니다.
			return elementData[nextIndex++];
		}
		
		// previous 메소드를 호출해도 되는지를 체크합니다.
		public boolean hasPrevious(){
			// nextIndex가 0보다 크다면 이전 엘리먼트가 존재한다는 의미입니다.
			return nextIndex > 0;
		}
		
		// 순차적으로 이전 노드를 리턴합니다.
		public Object previous(){
			// 이전 엘리먼트를 리턴하고 nextIndex의 값을 1감소합니다. 
			return elementData[--nextIndex];
		}
		
		// 현재 엘리먼트를 추가합니다. 
		public void add(Object element){
			ArrayList.this.add(nextIndex++, element);
		}
		
		// 현재 엘리먼트를 삭제합니다. 
        public void remove(){
            ArrayList.this.remove(nextIndex-1);
            nextIndex--;
        }
		

	}

}

댓글

댓글 본문
  1. 코딩이취미다
    상속과 Object 클래스에 대한 공부를 먼저 하고
    다시 오겠습니다.
    후다닥....
    답글
  2. 박찬혁
    맞습니다
    대화보기
      답글
    • 김아영
      제네릭을 사용하여 구현하고자 하는데요 반복자를 구현하는 부분에서 에러가 납니다 ㅜㅜ
      반복자 제네릭을 어떤방식으로 구현해야할까요?


      public class ArrayList<E> {

      ArrayList의 필드와 메소드 ...

      public ListIterator<E> listIterator() {
      return new ListIterator<E>();
      }
      public class ListIterator<E> {

      private int nextIndex = 0;


      public boolean hasNext() {
      return nextIndex < size();
      }


      public E next() {
      return elementData[nextIndex++];
      }
      }
      }
      답글
    • ssimba323@gmail.com
      remove 에서 에러가 납니다


      Exception in thread “main” java.lang.ArrayIndexOutOfBoundsException: -1

      이라고 나오면서 remove 부터 진행잉 안되는데 어쩌죠? ㅠㅠ
      답글수정삭제
    • 이상훈
      public class ListIterator 안에

      public void resetindex() {
      nextIndex=0;
      }

      만들거나,

      li = numbers.listIterator(); 를 다시 호출하시면 어떨까요. (초보자입니다.)
      대화보기
        답글
      • 지나가던 개발자
        안녕하세요^^. 게시해주신 글을 통해 자료구조를 학습해나가고 있는 사람입니다.
        해당 글을 읽는 중에 데이터 확인이라는 부분에서 "데이터를 확인하기 위해서 toString 객체를 상속해서 구현하겠습니다." 라고 적어 놓으셨는데, toString 객체가 아닌 toString 메소드를 오버라이드하였다라고 표현을 해야 맞는 것 아닌가요? toString은 객체가 아니니까요.
        답글수정삭제
      • 질문
        2번째 강의 질문있습니다. 메인클라스에 numbers.addLast(10);부분에서 addLast(10);부분에 에러가 나면서 addLast(Object)를 addLast(int)로 바꾸라고 나오는데 어떻게 해결해야 하나요?
        답글수정삭제
      • 질문
        질문3.
        9번째 동영상 다시 질문입니다..

        ArrayList.ListIterator li = numbers.listIterator();
        위에서 li 변수를 생성할 때, ArrayList.ListIterator가 직접 생성자 역할을 할 수 없는 이유가 무엇인가요?

        즉,
        ArrayList.ListIterator li = new ArrayList.ListIterator();
        위 코드처럼 생성하면 컴파일에러가 발생하는 이유가 궁금합니다
        답글수정삭제
      • 질문
        질문2.
        9번째 동영상 추가질문!!

        마지막에 hasNext메소드와 next메소드를 이용해서 while문을 통해 모든 원소내용을 출력하셨는데요
        문제는 그 이후에 만약 한 번 더 똑같은 출력작업을 하고 싶은 경우가 생긴다면,
        nextIndex값을 다시 0으로 초기화 해주어야 하잖아요?
        Main클래스에서 초기화하려면 nextIndex의 접근제어자를 private에서 다른걸로 바꿔줘야 할텐데,
        그러지 않고 ArrayList.java의 소스를 수정해서 해결하는 방법이 있나요?
        제가 고민해봐도 좋은 수가 안떠올라서 질문드립니다
        답글수정삭제
      • 질문
        9번째 동영상(반복)에서..
        ArrayList클래스 내부에 ListIterator 클래스를 구현할 때 public으로 생성하라는 팝업이 뜨던데,
        그렇게 표시하신 이유가 따로 있나요? 같은 패키지 내에 있으면 default로 생성해도 상관없지 않나요?
        답글수정삭제
      • whybe
        안녕하세요. 강의 감사히 잘듣고 있습니다 :)
        10번 동영상의 4분쯤에 여러 줄에 선언된 li.next(); 를 System.out.println();으로 감싸신거 단축키 좀 알 수 있을까요?
        1시간 넘게 찾아봤는데 도저히 못찾겠네요;;
        답글수정삭제
      • 머머
        참, 이고잉님 그리고 같이 공부하는 동료 여러분 모두 즐거운 명절되세요~~
        답글
      • 머머
        add 메소드 구현하고 addfirst 메소드 구현할때.. 잠시 영상 멈추고 add 메소드에 있는 로직 배껴다가 거의 비슷한 코드를 작성했는데 동영상 재생해보니 add메소드 재사용.. 머리통을 후려맞은 느낌입니다. 언제쯤이면 익숙해질까요?ㅠㅠ
        답글
      • Jason lee
        Object 쓰실때 O를 대문자로 쓰셔야하는데 소문자로 쓰셔서 그럴겁니다.
        대화보기
          답글수정삭제
        • 큰곰씨
          질문있습니다~!
          수업 매우 잘 보고 있습니다.
          main 클래스에
          numbers.addLast(10); 을 넣으면 addLast(10); 부분에 에러가 나고, 에러를 보니 Object로 캐스팅하라고 나옵니다.
          캐스팅해도 에러는 그대로 나구요. 원인이 뭔지 모르겠습니다..

          ArrayList 클래스도 추가했고, 동영상에 나온 ArrayList - java 구현 2까지 코드 똑같이 했습니다.
          답글수정삭제
        • Jinoo
          궁금한점이 있어서 여쭤볼게요~
          자바 컬렉션프레임워크를 공부하다보면 add메소드 들이 boolean타입으로 리턴값을 갖는데
          그냥 쓸대는 생각못했는데, 구현하는거 보면서 의문이 생겨서요.
          왜 리턴타입이 boolean인가요??
          데이터를 리턴받는 변수에 대입하는것이 아닌데 void도 상관이 없나요?
          이유가 궁금하네요..;
          답글수정삭제
        • bepositive1223
          봤어요를 누르고 그냥 넘어갈수가 없네요...

          9번째 반복 부분에서 ..

          ArrayList.ListIterator li = numbers.listIterator(); 가 나오니 막히네요...

          자바에 대한 이해가 부족한건가요... ㅠㅠ
          답글
        • 만다니라덕후
          감사합니다 언제나 많이 배우고 있어요
          계속해서 좋은 강의 부탁드려요!!
          답글수정삭제
        • Kani
          좋은강의 감사드립니다. ^^
          답글수정삭제
        • 아라한사
          아라한사 : (..마..마지못해 하며) 네..네앱..^^; 업로드 시간차가 좀 있어도 그..그럴 생각입니다..
          대화보기
            답글
          • egoing
            교차투고해주실꺼죠? ㅎㅎ ^^
            대화보기
              답글
            • 아라한사
              오늘부터 밥먹으면서 보려구요. 이고잉님 항상 강의 감사드립니다 'ㅁ';;

              저도 제 개인정리용같은걸로.. 사이트를 만들긴했는데.. (사실 .. 광고도 넣고 싶고.. 제 맘대로 좀 만지작 하고픈 마음에;;)
              뭔가.. 생활코딩에서 분가한 느낌도 나고..-_-;
              사이트 이름도 100코딩이라..;; 아 중국산 가짜냄새도 좀 나는 느낌도 나서 괜시리 2% 찝찝한 느낌나네요 ㅎㅎ

              개발자들이야 뭐.. 만들고 싶은 것은 구현하고픈 마음 이해해주실거라 생각합니다 ^^;

              자바로 자료구조가 되어있어서 정말 좋습니다 .잘 보겠습니다 ~!~! ㅎㅎㅎ
              답글
            • amainlog
              삭제 항목 바로위에 ' 배열을 복사해서 배열의 크기를 학대합니다. '
              이 부분 학 -> 확 오타 있습니다~
              답글수정삭제