Claire's Study Note

[Think Data Structures] 01. ์ธํ„ฐํŽ˜์ด์Šค

by Hi.Claire
๋ฐ˜์‘ํ˜•

01. ์ธํ„ฐํŽ˜์ด์Šค

01-1. ๋ฆฌ์ŠคํŠธ๊ฐ€ ๋‘ ์ข…๋ฅ˜์ธ ์ด์œ 

์ด๋ฒˆ ์žฅ์—์„œ๋Š” interface์™€ ์ด๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ํด๋ž˜์Šค๋ฅผ ์‚ดํŽด๋ณธ๋‹ค.

๋ช‡ ๊ฐ€์ง€ ์˜ˆ์ œ์—์„œ ArrayList, LinkedList์™€ ์œ ์‚ฌํ•œ ํด๋ž˜์Šค๋ฅผ ๊ตฌํ˜„ํ•˜๋ฉฐ ์ด๋“ค์˜ ๋™์ž‘ ๋ฐฉ๋ฒ•๊ณผ ๊ฐ๊ฐ์˜ ์žฅ๋‹จ์ ์— ๋Œ€ํ•ด ์•Œ์•„๋ณด์ž.

 

01-2. ์ž๋ฐ” interface

์ž๋ฐ” interface๋Š” ๋ฉ”์†Œ๋“œ ์ง‘ํ•ฉ์„ ์˜๋ฏธํ•œ๋‹ค.

์ด interface๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ํด๋ž˜์Šค๋Š” ์ด๋Ÿฌํ•œ ๋ฉ”์†Œ๋“œ๋ฅผ ์ œ๊ณตํ•ด์•ผ ํ•œ๋‹ค.

 

์˜ˆ์‹œ1. Comparable interface

public interface Comparable<T> {
    public int compareTo(T o);
}

์ด interface๋Š” ํƒ€์ž… ํŒŒ๋ผ๋ฏธํ„ฐ์ธ T๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ Comparable์ด๋ผ๋Š” ์ œ๋„ค๋ฆญ ํƒ€์ž…์„ ์ •์˜ํ•œ๋‹ค.

์ด interface๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ํด๋ž˜์Šค๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์•„์•ผ ํ•œ๋‹ค.

  • T ํƒ€์ž…์„ ๋ช…์‹œํ•ด์•ผ ํ•œ๋‹ค.
  • T ํƒ€์ž…์˜ ๊ฐ์ฒด๋ฅผ ์ธ์ž๋กœ ๋ฐ›๊ณ  int๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” compareTo ๋ฉ”์†Œ๋“œ๋ฅผ ์ œ๊ณตํ•ด์•ผ ํ•œ๋‹ค.

 

์˜ˆ์‹œ2. Integer ํด๋ž˜์Šค

public class Integer extends Number implements Comparable<Integer> {
    @Override
    public int compareTo(Integer anotherInteger) {
        int thisVal = this.value;
        int anotherVal = anotherInteger.value;
        return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
    }
    
    // ๋‹ค๋ฅธ ๋ฉ”์†Œ๋“œ ์ƒ๋žต
}

์ด ํด๋ž˜์Šค๋Š” Number ํด๋ž˜์Šค๋ฅผ extendsํ•˜์—ฌ Number ํด๋ž˜์Šค์˜ ๋ฉ”์†Œ๋“œ์™€ ์ธ์Šคํ„ด์Šค ๋ณ€์ˆ˜๋ฅผ ์ƒ์†ํ•œ๋‹ค.

๋˜ํ•œ Comparable<Integer> interface๋ฅผ ๊ตฌํ˜„ํ•˜์—ฌ Integer ๊ฐ์ฒด๋ฅผ ์ธ์ž๋กœ ๋ฐ›๊ณ  int๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” compareTo ๋ฉ”์†Œ๋“œ๋ฅผ ์ œ๊ณตํ•œ๋‹ค.

ํด๋ž˜์Šค๊ฐ€ interface๋ฅผ ๊ตฌํ˜„ํ•œ๋‹ค๊ณ  ์„ ์–ธํ•˜๋ฉด ์ปดํŒŒ์ผ๋Ÿฌ๋Š” interface๊ฐ€ ์ •์˜ํ•œ ๋ชจ๋“  ๋ฉ”์†Œ๋“œ๋ฅผ ์ œ๊ณตํ•˜๋Š”์ง€ ํ™•์ธํ•œ๋‹ค.

 

01-3. List interface

JCF๋Š” List๋ผ๋Š” interface๋ฅผ ์ •์˜ํ•˜๊ณ  ArrayList์™€ LinkedList๋ผ๋Š” ๋‘ ๊ตฌํ˜„ ํด๋ž˜์Šค๋ฅผ ์ œ๊ณตํ•œ๋‹ค.

interface๋Š” List๊ฐ€ ๋œ๋‹ค๋Š” ์˜๋ฏธ๊ฐ€ ๋ฌด์—‡์ธ์ง€๋ฅผ ์ •์˜ํ•œ๋‹ค. ์ด interface๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ํด๋ž˜์Šค๋Š” add, get, remove ๋“ฑ์„ ํฌํ•จํ•˜๋Š” ์•ฝ 20๊ฐ€์ง€ ๋ฉ”์†Œ๋“œ ์ง‘ํ•ฉ์„ ์ œ๊ณตํ•ด์•ผ ํ•œ๋‹ค.

ArrayList์™€ LinkedList ํด๋ž˜์Šค๋Š” ์ด๋Ÿฌํ•œ ๋ฉ”์†Œ๋“œ๋ฅผ ์ œ๊ณตํ•˜๋ฏ€๋กœ ์ƒํ˜ธ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ๋‹ค.

List๋กœ ๋™์ž‘ํ•˜๋Š” ๋ฉ”์†Œ๋“œ๋Š” ArrayList์™€ LinkedList ๋˜๋Š” List๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ์–ด๋–ค ๊ฐ์ฒด์™€๋„ ์ž˜ ๋™์ž‘ํ•œ๋‹ค.

 

์˜ˆ์‹œ1. ListClientExample

package com.allendowney.thinkdast;

import java.util.LinkedList;
import java.util.List;

public class ListClientExample {
	@SuppressWarnings("rawtypes")
	private List list;

	@SuppressWarnings("rawtypes")
	public ListClientExample() {
		list = new LinkedList();
	}

	@SuppressWarnings("rawtypes")
	public List getList() {
		return list;
	}

	public static void main(String[] args) {
		ListClientExample lce = new ListClientExample();
		@SuppressWarnings("rawtypes")
		List list = lce.getList();
		System.out.println(list);
	}
}

ListClientExample ํด๋ž˜์Šค๋Š” List๋ฅผ ์บก์Аํ™”ํ•˜๋Š” ํด๋ž˜์Šค์˜ ํ•„์ˆ˜ ์š”์†Œ(Listํ˜•์˜ ์ธ์Šคํ„ด์Šค ๋ณ€์ˆ˜)๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.

์ด ์˜ˆ์ œ์˜ ์ค‘์š”ํ•œ ์ ์€ ํ•„์š”ํ•œ ๊ฒฝ์šฐ๊ฐ€ ์•„๋‹ˆ๋ฉด ArrayList๋‚˜ LinkedList ๊ฐ™์€ ๊ตฌํ˜„ ํด๋ž˜์Šค๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ๊ฐ€๋Šฅํ•œ ํ•œ List interface๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค๋Š” ์ ์ด๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์ธ์Šคํ„ด์Šค ๋ณ€์ˆ˜๋Š” List interface๋กœ ์„ ์–ธํ•˜๊ณ  getList ๋ฉ”์†Œ๋“œ๋Š” Listํ˜•์„ ๋ฐ˜ํ™˜ํ•˜์ง€๋งŒ ๊ตฌ์ฒด์ ์ธ ํด๋ž˜์Šค๋Š” ์–ธ๊ธ‰ํ•˜์ง€ ์•Š๋Š”๋‹ค.

๋งˆ์Œ์„ ๋ฐ”๊ฟ” ArrayList๋ฅผ ์‚ฌ์šฉํ•˜๊ณ ์ž ํ•œ๋‹ค๋ฉด ์ƒ์„ฑ์ž๋งŒ ๋ฐ”๊พธ๋ฉด ๋˜๊ณ  ๋‚˜๋จธ์ง€๋Š” ๊ทธ๋Œ€๋กœ ๋‘๋ฉด ๋œ๋‹ค.

์ด๋Ÿฌํ•œ ์Šคํƒ€์ผ์„ ์ธํ„ฐํŽ˜์ด์Šค ๊ธฐ๋ฐ˜ ํ”„๋กœ๊ทธ๋ž˜๋ฐ(interface-based programming) ๋˜๋Š” ์ธํ„ฐํŽ˜์ด์Šค ํ”„๋กœ๊ทธ๋ž˜๋ฐ(interface programming)์ด๋ผ๊ณ  ํ•œ๋‹ค.

๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ ์ฝ”๋“œ๋Š” ์˜ค์ง List์™€ ๊ฐ™์€ interface๋งŒ ์˜์กดํ•˜๊ณ  ArrayList ํด๋ž˜์Šค์™€ ๊ฐ™์€ ํŠน์ • ๊ตฌํ˜„์— ์˜์กดํ•ด์„œ๋Š” ์•ˆ ๋œ๋‹ค.

์ด๋Ÿฌํ•œ ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•˜๋ฉด ๋‚˜์ค‘์— ๊ตฌํ˜„์ด ๋ณ€๊ฒฝ๋˜์–ด๋„ interface๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ์ฝ”๋“œ๋Š” ๊ทธ๋Œ€๋กœ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค.

๋ฐ˜๋ฉด์— interface๊ฐ€ ๋ณ€๊ฒฝ๋œ๋‹ค๋ฉด interface๋ฅผ ์˜์กดํ•˜๋Š” ์ฝ”๋“œ๋Š” ๋ณ€๊ฒฝ๋˜์–ด์•ผ ํ•œ๋‹ค.

์ด ๋•Œ๋ฌธ์— ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ๊ฐœ๋ฐœ์ž๋Š” ๊ผญ ํ•„์š”ํ•œ ์ผ์ด ์•„๋‹ˆ๋ฉด interface๋ฅผ ์ž˜ ๋ณ€๊ฒฝํ•˜์ง€ ์•Š๋Š”๋‹ค.

 

01-4. ์‹ค์Šต 1

์˜ˆ์‹œ1. ListClientExampleTest

package com.allendowney.thinkdast;

import static org.junit.Assert.assertThat;
import static org.hamcrest.CoreMatchers.*;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
 * @author downey
 *
 */
public class ListClientExampleTest {

	/**
	 * Test method for {@link ListClientExample}.
	 */
	@Test
	public void testListClientExample() {
		ListClientExample lce = new ListClientExample();
		@SuppressWarnings("rawtypes")
		List list = lce.getList();
		assertThat(list, instanceOf(ArrayList.class) );
	}

}

์ด ํด๋ž˜์Šค๋Š” ListClientExample ํด๋ž˜์Šค์— ๋Œ€ํ•œ JUnit ์ฝ”๋“œ์ด๋‹ค.

์ด ํด๋ž˜์Šค์—์„œ๋Š” ํ•œ ๊ฐ€์ง€ ํ…Œ์ŠคํŠธ๋ฅผ ์‹คํ–‰ํ•˜๋Š”๋ฐ, ListClientExample ํด๋ž˜์Šค์˜ getList() ๋ฉ”์†Œ๋“œ๋ฅผ ์‹คํ–‰ํ•˜์—ฌ ์ด ๋ฉ”์†Œ๋“œ์˜ ๋ฐ˜ํ™˜ํ˜•์ด ArrayList ํด๋ž˜์Šค์ธ์ง€ ํ™•์ธํ•œ๋‹ค.

getList() ๋ฉ”์†Œ๋“œ๋Š” LinkedList ํด๋ž˜์Šค๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋ฏ€๋กœ ํ…Œ์ŠคํŠธ์— ์‹คํŒจํ•œ๋‹ค.

 

์—๋Ÿฌ ๋ฉ”์‹œ์ง€

java.lang.AssertionError: 
Expected: an instance of java.util.ArrayList
     but: <[]> is a java.util.LinkedList

 

๋‹ค์‹œ ListClientExample ํด๋ž˜์Šค์—์„œ ์ƒ์„ฑ์ž์˜ LinkedList๋ฅผ ArrayList๋กœ ๋Œ€์ฒดํ•˜๊ณ  ํ…Œ์ŠคํŠธ๋ฅผ ์‹คํ–‰ํ•˜๋ฉด ์„ฑ๊ณตํ•œ๋‹ค.

 

์ด ํ…Œ์ŠคํŠธ๋ฅผ ํ†ต๊ณผํ•˜๊ธฐ ์œ„ํ•ด ์ƒ์„ฑ์ž์—์„œ LinkedList ๊ฐ์ฒด ์ƒ์„ฑ ๋ถ€๋ถ„๋งŒ ๋ณ€๊ฒฝํ•˜์˜€๊ณ  List ์„ ์–ธ ๋ถ€๋ถ„์€ ๋ณ€๊ฒฝํ•˜์ง€ ์•Š์•˜๋‹ค.

์„ ์–ธ ๋ถ€๋ถ„์„ ArrayList๋กœ ๋ณ€๊ฒฝํ•ด๋„ ํ”„๋กœ๊ทธ๋žจ์€ ์ •์ƒ ๋™์ž‘ํ•œ๋‹ค.

ํ•˜์ง€๋งŒ ์ด๊ฒƒ์€ ๊ณผ๋‹ค ์ง€์ •(overspecified)์ด๋‹ค.

๋‚˜์ค‘์— ๋‹ค์‹œ interface๋กœ ๋Œ์•„๊ฐ€๋ ค๋ฉด ๋” ๋งŽ์€ ์ฝ”๋“œ๋ฅผ ์ˆ˜์ •ํ•ด์•ผ ํ•  ์ˆ˜๋„ ์žˆ๋‹ค.

 

๊ทธ๋ ‡๋‹ค๋ฉด ListClientExample ํด๋ž˜์Šค์˜ ์ƒ์„ฑ์ž์—์„œ ArrayList ๊ฐ์ฒด๋ฅผ List interface๋กœ ๊ต์ฒดํ•˜๋ฉด ์–ด๋–ป๊ฒŒ ๋ ๊นŒ?

์™œ List interface๋กœ๋Š” ์ธ์Šคํ„ด์Šค๊ฐ€ ์ƒ์„ฑ๋˜์ง€ ์•Š์„๊นŒ?

 

์—๋Ÿฌ๋ฉ”์‹œ์ง€

'List' is abstract; cannot be instantiated

 

 

๋ฐ˜์‘ํ˜•

๋ธ”๋กœ๊ทธ์˜ ์ •๋ณด

Claire's Study Note

Hi.Claire

ํ™œ๋™ํ•˜๊ธฐ