Java 자료구조 - List, Set, Map

- Collection 이란?

Collection은 자료구조 List, Set 의 구현 객체이다(Interface). 하지만 Map 같은경우 List, Set과 달리 Key-Value 라는 구조적인 차이가 있어 Collection Interface를 구현(상속)하지 안고 별도로 정의하고 있다.

 

List, Set 상속 관계

// ArrayList
public class ArrayList<E> extends AbstractList<E>

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

public abstract class AbstractCollection<E> implements Collection<E>

// HashSet
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>

public abstract class AbstractCollection<E> implements Collection<E>

위  코드를 보면 ArrayList, HashSet은 AbstractList, AbstractSet 를 상송하고있고 다시 AcAbstractCollection 이 Collection을 구현객체로 받아 정의하고있다.

 

 Collection Method

Method	Type	설명
add(E e)	boolean	해당 컬렉션에 전달된 요소를 추가
remove(Object o)	boolean	해당 컬렉션에서 전달된 객체를 제거
clear()	void	해당 컬렉션의 모든 요소를 제거
contains(Object o)	boolean	해당 컬렉션이 전달된 객체를 포함하고 있는지
equals(Object o)	boolean	해당 컬렉션과 전달된 객체가 같은지
isEmpty()	boolean	해당 컬렉션이 비어있는지
iterator()	Iterator	해당 컬렉션의 반복자(iterator)를 반환
size()	int	해당 컬렉션의 요소의 총개수를 반환
toArray()	int	해당 컬렉션의 모든 요소를 Object 타입의 배열로 반환

 

- List Inferface

• ArrayList, LinkedList 의 구현체이다. 물론 Vector, Stack은 지금은 사용하지안고 호환성을 위해 남아있는 Class 이다.

• 순서를 가진다

• 인덱스로 객체에 접근 할 수 있다.

Class	Base Class	Base Interface	중복 하영	순서 보장	정렬 여부
ArrayList	AbstractList	List	Yes	Yes	No
LinkedList	AbstractSequentialList	List;Deque	Yes	Yes	No

ArrayList

• 기본 배열(int[] a = new int[3])을 사용할때 해당 인덱스값이 다차여 더이상 값을 넣지 못하거나 인덱스를 다 못채워서 메모리가 낭비가 있을 수 있다 이러한 이유로 ArrayList 클래스를 사용한다.
• 객체의 삽입/삭제가 자주 있을 때에 ArrayList는 비효율적다. (중간 값을 수정시 해당 인댁스의 값을 수정하고 그 부분부터 순서에 맞게 다시 채워야 하기 때문이다.)

LinkedList

• LinkedList 는 ArrayList와 달리 여러 개의 객체들이 다음 객체의 정보를 가지고 있는 모양이므로 특정 값을 검색하는것이 ArrayList 보다는 느리다.
• LinkedList 는 index로 값을 저장하는것이 아니라 노드들의 주소를 값을 가지고 있기 때문에 객체의 삽입/삭제가 ArrayList보다 빠르다. (수정하고자하는 곳에 주소 값을 끊고 앞뒤 주소만 다시 메핑하면 나머지 노드들은 다시 정렬 할 필요가 없다)

구분	순차적으로 추가,검색	중간 추가,삭제	검색
ArrayList	빠르다	느리다	빠르다
LinkedList	느리다	빠르다	느리다

첫 번째 그림은 ArrayList, 두 번째 그림은 LinkedList 의 그림이다.

 

 

- Set Inferface

• HashSet, LinkedHashSet의 구현체 이다.

• 중복된 값을 허용 하지 안는다.

Class	Base Class	Base Interface	중복 하영	순서 보장	정렬 여부
HashSet	AbstractSet	Set	No	No	No
LinkedHashSet	HashSet	Set	No	Yes	No

HashSet

• 내부적으로 HashMap을 사용하여 값을 저장한다.
• 값의 중복을 허용 하지 안는다.
• 값이 저장된 순서를 보장하지 안는다.
• null 을 허용 한다.

LinkedHashSet

LinkedHash Set은 Linked라는 의미릴 보면 알 수 있듯이 객체의 주소들끼리 연결된 구조이기 때문에 값이 저장된 순서를 보장한다. 그 외에 특선은 HashSet과 공일하다.

 

※ hash: 임의의 크기를 간진 데이터를 고정된 데이터의 크기로 변환 이라고하는데 나는 값 과 메핑되여있는 고유한 값(주소:hash)이라고 외우고 있다.

 

- Map Inferface

• HashMap, LinkedHashMap, TreeMap의 구현체이다.
• key값은 중복될 수 없으며 중복된 값을 입력시 마지막 값이 저장된다.

Class	Base Class	Base Interface	중복 하영	순서 보장	정렬 여부
HashMap	AbstractMap	Map	No	No	No

HashMap

• null 인 key 와 null인 value를 허용한다.
• 저장된 순서를 보장하지 안는다.
• 중복된 key를 허용은아지만 마지막 값이 저장된다

LinkedHashMap

• 저장된 순서를 보장한다.

 

null을 허용한다. (왜 라는 질문이 있을 수 있어서 다음과 같이 코드를 보면서 설명하겠습니다.)

class Main() {
	public static void main(String[] args) {
    	Map<String, Integer> map = new HashMap<String, Integer>();
		map.put(null, null);
    }
}

 

 

자료구조에서는(위에서는 HashMap이다) 제네릭 타입을 지정할때 일반형이 아닌 Class 형 변수를 지정한다. (ex) String, Integer 등)그렇기 때문에 null을 포함고 있게때문에 사용할 수 있다. 

 

https://jktech.tistory.com/14

Java 참조 자료형(클래스, 인터페이스, 배역, 열겨 타입)

https://github.com/jkkim09/JAVA-BASE

jkkim09/JAVA-BASE