자바 [JAVA] - List Interface (리스트 인터페이스)

아무쪼록, 자료구조를 어려워 할 필요는 없다. 아니 초기에 이미 여러분들은 사용하고 있다. 바로 배열이다. int[] 나, double[] 같은 배열을 말하는 것이다. 다만, 자바 컬렉션 프레임워크에서 지원하는 ArrayList, LinkedLIst 같은 리스트 클래스들은 우리가 좀 더 데이터들을 다루기 쉽게 메소드들을 구현한 것이다.

그럼 배열하고 List 인터페이스에서 지원하는 클래스들(ex. ArrayList, LinkedList...)의 공통점과 차이점은 무엇인지 간단하게 설명하고 넘거가겠다.

[공통점]

1. 동일한 특성의 데이터들을 묶는다.

2. 반복문(loop)내에 변수를 이용하여 하나의 묶음 데이터들을 모두 접근할 수 있다.

[차이점 - 배열]

1. 처음 선언한 배열의 크기(길이)는 변경할 수 없다. 이를 정적 할당(static allocation)이라고 한다.

2. 메모리에 연속적으로 나열되어 할당된다.

3. index에 위치한 하나의 데이터(element)를 삭제하더라도 해당 index에는 빈공간으로 계속 남는다.

[차이점 - 리스트]

1. 리스트의 길이가 가변적이다. 이를 동적 할당(dynamic allocation)이라고 한다.

2. 데이터들이 연속적으로 나열된다. (메모리에 연속적으로 나열되지 않고 각 데이터들은 주소(reference)로 연결되어있다. C에서의 포인터라고 생각하면 된다.)

3. 데이터(element) 사이에 빈 공간을 허용하지 않는다.

공통점보다는 차이점이 많은데 이에 따른 장단점도 매우 명확하다.

[배열의 장단점]

<장점>

1. 데이터 크기가 정해져있을 경우 메모리 관리가 편하다.

2. 메모리에 연속적으로 나열되어 할당하기 때문에 index를 통한 색인(접근)속도가 빠르다.

<단점>

1. 배열의 크기를 변경할 수 없기 때문에 초기에 너무 큰 크기로 설정해주었을 경우 메모리 낭비가 심해지고, 반대로 너무 작은 크기로 설정해주었을 경우 데이터를 다 못담을 수 있는 경우가 발생 할 수 있다.

2. 데이터를 삽입(add), 삭제(remove)를 할 때 빈 공간을 허용하지 않고자 한다면, 뒤의 데이터들을 모두 밀어내거나 당여주어야 하기 때문에 속도가 느려 삽입, 삭제가 빈번한 경우에는 유용하지 않다.

[리스트의 장단점]

<장점>

1. 데이터의 개수에 따라 해당 개수만큼 메모리를 동적 할당해주기 때문에 메모리 관리가 편리해진다.

2. 빈 공간을 허용하지 않기 때문에 데이터 관리에도 편하다.

3. 포인터(주소)로 각 데이터들이 연결되어 있기 때문에 해당 데이터에 연결된 주소만 바꿔주면 되기 때문에 삽입 삭제에 용이하다.(ArrayList는 예외)

<단점>

1. 객체로 데이터를 다루기 때문에 적은양의 데이터만 쓸 경우 배열에 비해 차지하는 메모리가 커진다.

간단히 예로들어 primitive type인 Int는 4Byte를 차지한다. 반면에 Wraaper class인 Integer는 32bit JVM에선 객체의 헤더(8Byte), 원시 필드(4Byte), 패딩(4Byte)으로 '최소 16Byte를 차지한다. 거기에다가 이러한 객체데이터들을 다시 주소로 연결하기 때문에 16 + α 가 된다.

2. 기본적으로 주소를 기반으로 구성되어있고 메모리에 순차적으로 할당하는 것이 아니기 때문에(물리적 주소가 순차적이지 않다) 색인(검색)능력은 떨어진다.

대강 이정도로만 알아두도록 하자. ArrayList와 LinkedList도 이 둘의 장단점이 달라 앞으로 좀 더 자세하게 ArrayList, LinkedList들을 구현해보면서 한 번 더 꼼꼼하게 알려주겠다.

그럼 이제 List 인터페이스에 구현된 메소드들을 살펴보아야 겠다. 여기서 모든 메소드들을 살펴볼 수는 없고, 몇가지 자주 사용하는 메소드들이 있다.

<List Interface에 선언된 대표적인 메소드>

자바 컬렉션 프레임워크 글에서도 언급했지만, List Interface에서 대표적으로 위와 같은 메소드들이 있다. 실제로는 더 많은 추상메소드들이 있는데, 자세한 내용은 아래 Java API 에서 잘 설명해주고 있으니 한 번 확인해보는 것도 앞으로 구현하는데 도움이 될 것이다.

docs.oracle.com/en/java/javase/13/docs/api/java.base/java/util/ArrayList.html

ArrayList (Java SE 13 & JDK 13 )

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is

docs.oracle.com

자바에서 제공해주고 있는 컬렉션들과 마찬가지로 필자도 앞으로 자료구조를 구현할 때 비슷한 계열들은 Interface를 사용하여 메소드들을 선언해줄 것이다.

자료구조를 배우는 정도까지 왔다면 알겠지만, 혹시나 하여 인터페이스에 대해 말해드리자면, Interface는 추상메소드(구현되지 않고 선언만 된 메소드)들의 모임이다. 이 Interface를 어느 객체에서 상속하여 사용하게 되면, 그 객체는 Interface에 선언된 추상메소드들을 '반드시' 강제적으로 구현해주어야 한다.

이는 다형성이라는 Java의 대표적 특징이다. 보통 상속(extend)와 많이 헷갈려하기 때문에 잠깐 정리해주고 가겠다.

일반적으로 클래스 상속(extend)의 경우 이미 만들어진 클래스와 그 안의 메소드들을 자식클래스가 사용할 수 있게 만드는 것이다. 즉, 상위(부모) 클래스의 모든 메소드들을 사용할 수 있다는 장점은 있지만, 반대로 어느 한쪽에서 변화가 생긴다면 상속관계가 깨져버린다는 것이다. 예로들어 부모클래스에 '덧셈' 이라는 기능이 추가되었는데, 자식클래스에서 '덧셈'기능을 사용하지 못하도록 해야할 때 상속관계가 깨져버린다는 것이다.

반대로 인터페이스(Interface)의 경우 메커니즘이 다르다. 추상메소드로만 구현되어있기 때문에 이를 상속한 클래스는 반드시 재정의(Override)를 하여 '구현'을 필수로 하게 만든다. 그래서 Interface를 상속하는 방법 또한 extend가 아닌 implements 다. (보통 자바에서는 구현이라고 표현하는데, 상속이라 해도 의미는 통하니 크게 문제되진 않는다.) 이러한 메커니즘으로 인터페이스를 구현한 객체들은 같은 동작을 보장한다는 장점이 있다.

예로들어 A라는 Interface가 있고 그 안에 2의 n승을 구해주는 메소드인 power_Of_2()라는 메소드가 있다고 한다. 그리고 class B와 class C가 있다고 가정해보자.

Interface A {
	// 2의 n승을 구해주는 메소드
	public int power_Of_2(int n);	// 추상메소드
}

class B implements A {	// A를 상속(구현)
	// 메소드 재정의 
	@Override	
	public int power_Of_2(int n) {

		int result = 1;
		for(int i = 0; i < n; i++) {
			result = result * 2;
		}
		return result;
	}
}

class C implements A {	// A를 상속(구현)
	// 메소드 재정의
	@Override	
	public int power_Of_2(int n) {

		int result = (1 << n);
		return result;
	}
}

보면 클래스 B와 C는 서로 구하는 방식은 달라도 결국 2의 n승을 구하기 위한 동작은 같다. 이렇게 어떠한 규약을 정해놓고 관리하기 쉽게 할 수 있는 것이 바로 interface다.

또한 같은 interface를 구현하지만 B클래스의 성능이 너무 느려 A클래스의 메소드로 대체하고자 할 때, 그대로 사용하면 된다는 장점이 있다.

그럼 이를 토대로 앞으로 구현 할 인터페이스를 만들어보자. 또한 여러분들도 자료구조를 만들고자 할 때, 인터페이스들은 같은 프로젝트 폴더 안에 다른 package를 하나 만들어서 그 안에 모아놓는 것을 추천한다.(필자는 Interface_form이라는 패키지에 저장할 것이다.)

그리고 필자는 이를 토대로 앞으로 구현해나갈 것이니 참고하시길.

package Interface_form;

/**
 * 
 * 자바 List Interface입니다. <br>
 * List는 ArrayList, SinglyLinkedList, DoublyLinked에 의해 각각 구현됩니다.
 * 
 * @author st_lab
 * @param <E> the type of elements in this list
 *
 * @version 1.0
 * 
 */

public interface List<E> {

	/**
	 * 리스트에 요소를 추가합니다.
	 * 
	 * @param value 리스트에 추가할 요소
	 * @return 리스트에서 중복을 허용하지 않을 경우에 리스트에 이미 중복되는 
	 *         요소가 있을 경우 {@code false}를 반환하고, 중복되는 원소가
	 *         없을경우 {@code true}를 반환
	 */
	boolean add(E value);

	/**
	 * 리스트에 요소를 특정 위치에 추가합니다. 
	 * 특정 위치 및 이후의 요소들은 한 칸씩 뒤로 밀립니다.
	 * 
	 * @param index 리스트에 요소를 추가할 특정 위치 변수
	 * @param value 리스트에 추가할 요소
	 */
	void add(int index, E value);

	/**
	 * 리스트의 index 위치에 있는 요소를 삭제합니다.
	 * 
	 * @param index 리스트에서 삭제 할 위치 변수
	 * @return 삭제된 요소를 반환
	 */
	E remove(int index);

	/**
	 * 리스트에서 특정 요소를 삭제합니다. 동일한 요소가 
	 * 여러 개일 경우 가장 처음 발견한 요소만 삭제됩니다.
	 * 
	 * @param value 리스트에서 삭제할 요소
	 * @return 리스트에 삭제할 요소가 없거나 삭제에 실패할 
	 *         경우 {@code false}를 반환하고 삭제에 성공할 경우 {@code true}를 반환 
	 */
	boolean remove(Object value);

	/**
	 * 리스트에 있는 특정 위치의 요소를 반환합니다.
	 * 
	 * @param index 리스트에 접근할 위치 변수 
	 * @return 리스트의 index 위치에 있는 요소 반환 
	 */
	E get(int index);

	/**
	 * 리스트에서 특정 위치에 있는 요소를 새 요소로 대체합니다.
	 * 
	 * @param index 리스트에 접근할 위치 변수 
	 * @param value 새로 대체할 요소 변수 
	 */
	void set(int index, E value);

	/**
	 * 리스트에 특정 요소가 리스트에 있는지 여부를 확인합니다.
	 * 
	 * @param value 리스트에서 찾을 특정 요소 변수 
	 * @return 리스트에 특정 요소가 존재할 경우 {@code true}, 존재하지 않을 경우 {@code false}를 반환  
	 */
	boolean contains(Object value);

	/**
	 * 리스트에 특정 요소가 몇 번째 위치에 있는지를 반환합니다.
	 * 
	 * @param value 리스트에서 위치를 찾을 요소 변수  
	 * @return 리스트에서 처음으로 요소와 일치하는 위치를 반환.
	 *         만약 일치하는 요소가 없을경우 -1 을 반환 
	 */
	int indexOf(Object value);

	/**
	 * 리스트에 있는 요소의 개수를 반환합니다.
	 * 
	 * @return 리스트에 있는 요소 개수를 반환  
	 */
	int size();

	/**
	 * 리스트에 요소가 비어있는지를 반환합니다.
	 * @return 리스트에 요소가 없을경우 {@code true}, 요소가 있을경우 {@code false}를 반환 
	 */
	boolean isEmpty();

	/**
	 * 리스트에 있는 요소를 모두 삭제합니다.
	 */
	public void clear();

}

그리고 앞으로 자료구조들을 구현할 때 몇가지 규칙을 정할 것이다.

1. 제네릭(Generic)은 한 개일 경우 E, 두 개일 경우 E와 T로 표현할 것이다. 보통 많이 쓰이는 제네릭 이름은 T, K, V, E가 많기 때문에 필자도 대표적인 E와 T로 쓰고자 한다.

2. 최대한 Java API 문서에 나와있는 제공되는 메소드들과 유사하게 만들 것이다. 기준은 아래 링크에서 보면 된다. docs.oracle.com/en/java/javase/11/docs/api/index.html

3. 기본적으로 여러분들이 재정의(Override), 예외처리(throw), 객체(Object), 인터페이스(nterface), 제네릭(Generic) 이렇게 5개에 대한 기본 지식은 있다는 전제하에 설명 할 것이다. 그렇지 않고 하나하나 설명하다보면 길이 너무 길어져 핵심을 못짚게 되어 결정했다.

또한 포스팅과 동시에 아래 깃허브에도 전체 소스를 올릴 것이니 필요하신 분은 참고하셔도 된다.

github Data_Structure

kdgyun/Data_Structure

Contribute to kdgyun/Data_Structure development by creating an account on GitHub.

github.com

정리

오늘은 간단하게 List와 배열의 차이 및 장단점을 알아보고 앞으로 사용할 List Interface를 간단하게 만들어놓았다. 이를 토대로 ArrayList와 LinkedList를 만들 것이다. 혹여 앞으로의 포스팅에 있어 모르거나 헷갈리는 것이 있다면 언제든 댓글 남겨주시면 감사하겠다.

물론 자료구조 자체가 프로그래밍 입문 후 대개 첫번째 난관으로 말할 만큼 쉽지는 않은 내용이긴하나, 필자도 최대한 쉽게 구현하고 만들 수 있도록 최대한 노력하겠다. 이러한 과정 중에 혹여 지적할 부분이 있다면 언제든 댓글 남겨주시면 빠르게 피드백하여 수정할 것은 수정하고, 보완할 점은 보완할 것이니 부담없이 댓글 남겨주시길 바란다.

저작자표시 비영리 변경금지

'자료구조 > Java' 카테고리의 다른 글

자바 [JAVA] - Stack Interface (스택 인터페이스) (12)	2020.11.19
자바 [JAVA] - Doubly LinkedList (이중 연결리스트) 구현하기 (12)	2020.11.18
자바 [JAVA] - Singly LinkedList (단일 연결리스트) 구현하기 (41)	2020.11.08
자바 [JAVA] - ArrayList (어레이리스트) 구현하기 (42)	2020.10.29
자바 [JAVA] - 자바 컬렉션 프레임워크 (Java Collections Framework) (49)	2020.09.21

자바 [JAVA] - List Interface (리스트 인터페이스)

'자료구조 > Java' 카테고리의 다른 글

댓글

이 글 공유하기

티스토리툴바

'자료구조 > Java' 카테고리의 다른 글

댓글

이 글 공유하기

다른 글

자바 [JAVA] - Doubly LinkedList (이중 연결리스트) 구현하기

자바 [JAVA] - Singly LinkedList (단일 연결리스트) 구현하기

자바 [JAVA] - ArrayList (어레이리스트) 구현하기

자바 [JAVA] - 자바 컬렉션 프레임워크 (Java Collections Framework)

티스토리툴바