상위문서 : 자료구조
필수참고문서 : 연결리스트
목차
1. 개요
2. 설명
3. 구현
3.1. JAVA로 구현
3.2. C#으로 구현
3.2. C#으로 구현
1.개요
맵은 키와 값을 가지고 있는 엔트리의 집합이다. 맵의 특징은 같은 키를 가지고 있는 엔트리는 허용하지 않는 다는것인데 먼저 3이라는 키로 엔트리가 들어오면 나중에 3이라고 들어온 엔트리로 그 교체해버리고 예전에 있던 엔트리의 값을 반환한다. 또한 맵에서 중요한게 iterator(반복자)도 알아야하는데
먼저 이터레이터가 가지고 있는 매서드를 필수적으로 알아야한다.
- hasNext() - 다음 값이 있는지 확인하는 매서드이다. 있으면 true 없으면 false를 리턴한다.
- next() - 다음 값을 리턴한다.
- remove() : 삭제
의 매서드를 가지고 있는데 이때 게임 제목과 키들을 넣은 맵에서 다음과 같이 쓸 수 있다.
iterator<Entry> map=game.iterator();
이렇게 되면 map이라는 변수안에 Entry 형태의 모든 값들이 저장된다. 일단 제일 앞에 있는 엔트리를 가르키게 되는데
while(map.hasNext())을 하면 map의 끝까지 돌 수 있다.
또한 map.value.next() 로 위의 while과 결합하면 값을 처음부터 끝까지 가져올 수 있는 것이다.
맵의 구현은 이중 연결리스트로 한다.
딕셔너리는 키로 항목 검색이 가능한 셋이다. 딕셔너리로 할 수 있는 작업은 맵과 99%동일한데 한가지가 차이가 난다. 바로 같은 키를 가지는 엔트리를 여러개 가질 수 있다는 것이다.
딕셔너리 또한 구현은 이중 연결리스트로 한다.
딕셔너리 또한 구현은 이중 연결리스트로 한다.
2.설명
맵의 ADT는 다음과 같다.
- get(key) : 맵에서 입력받은 키에 해당하는 엔트리가 있을경우 값을 돌려주고 없으면 null을 돌려준다. O(n)
- put(key, value) : 맵에 엔트리를 넣는다. 만약 입력받은 키에 해당되는 엔트리가 없을 경우 넣는것이 성공하며 null을 반환한다. 만약 이미 있으면 키에 해당하는 값을 반환하고 새 값을 넣는다.
- remove(key) : 입력받은 키에 해당하는 엔트리를 삭제한다.
- size(), isEmpty() : 약방의 감초 맵에 엔트리가 몇개있는지 알아보는 사이즈와 맵이 비어있는지 확인하는 이즈엠피티다.
- keys() : 현재 맵에 있는 모든 키를 반환한다. 반환형태는 iterator로 반환
- values() : 현재 맵에 있는 모든 값을 반환한다. 반환형태는 iterator로 반환
딕셔너리의 ADT는 다음과 같다.
- find(key) : 입력받은 키에 해당하는 엔트리가 있을 경우 값을 돌려주고 없으면 null을 돌려준다.
- findAll(key) : 같은 키의 엔트리의 값을 전부 반환한다. 반환값은 iterator로 반환한다.
- insert(key, value) : 엔트리를 넣는다. 키가 중복되도 되기때문에 실패할 경우가 없다.
- remove(key) : 입력받은 키에 해당하는 엔트리를 삭제한다.
- entries() : 딕셔너리 전체에 있는 모든 엔트리를 반환한다. 이 역시 반환 형태는 iterator이다...
- size(), isEmpty() : 말안해도 알듯
여기서 중요한 것은 딕셔너리는 중복된 값을 넣을 수 있는데 remove와 find 연산시 처음 넣은 값과 나중 넣은 값 어떤것이 먼저 나오냐 하면 처음 넣은 값이 먼저 나온다. 나중에 넣은 값은 처음 넣은 값을 삭제해야 한다. 아니면 findAll을 사용하여 볼 수도 있다.
