연결 리스트를 이용한 순차 검색

Symbol Table이란?

ㆍ (키, 값) 쌍이 모인 자료구조

ㆍ 특정 키와 그 키에 해당되는 값의 쌍을 삽입할 수 있다.

ㆍ 키가 주어질 때, 관련된 값을 검색할 수 있다.

---

연결 리스트를 이용한 Symbol Table의 동작 방법

---

구현 방법

노드의 구성

class Node<K, V> {
	K key;
	V value;
	Node<K, V> next;

	public Node(K key, V value, Node<K, V> next) {
		this.key = key;
		this.value = value;
		this.next = next;
	}
}

ㆍ 노드는 키, 값, 다음 노드를 가리키는 참조로 구성되어 있다.

 

Symbol Table의 기본 구성

public class SequentialSearchST<K, V> {
	private Node<K, V> first;
	int N;
}

ㆍ 첫 번째 노드에 대한 참조 변수인 first가 있다.
ㆍ 연결 리스트의 노드 수에 대한 변수인 N이 있다.

 

get() 메서드

public V get(K key) {
	for (Node<K, V> x = first; x != null; x = x.next)
		if (key.equals(x.key))
			return x.value;

	return null;
}

ㆍ 연결 리스트를 처음부터 스캔한다.
ㆍ 검색하고자 하는 키를 찾았으면 키에 대응하는 값을 리턴한다.
ㆍ 찾지 못했으면 null을 리턴한다.

 

put() 메서드

public void put(K key, V value) {
	for (Node<K, V> x = first; x != null; x = x.next)
		if (key.equals(x.key)) {
			x.value = value;
			return;
		}
	first = new Node<K, V>(key, value, first);
	N++;
}

ㆍ 연결 리스트를 처음부터 스캔한다.
ㆍ 만약 해당 키가 있을 경우 값만 바꾼다.
ㆍ 해당 키가 없을 경우 새로운 (키, 값) 쌍을 추가하고, 전체 노드의 수를 1 증가시킨다.

 

delete() 메서드

public void delete(K key) {
	if (key.equals(first.key)) { 
		first = first.next;
		N--;
		return;
	}

	for (Node<K, V> x = first; x.next != null; x = x.next) {
		if (key.equals(x.next.key)) {
			x.next = x.next.next;
			N--;
			return;
		}
	}
}

ㆍ 첫 번째 노드의 키가 삭제할 키와 일치한다면 첫 번째 노드를 삭제한다.
ㆍ 첫 번째 노드를 삭제하지 않는 경우는 연결 리스트를 처음부터 스캔하고, 삭제할 노드를 찾는다.

 

keys() 메서드

public Iterable<K> keys() {
	ArrayList<K> keyList = new ArrayList<K>(N);

	for (Node<K, V> x = first; x != null; x = x.next)
		keyList.add(x.key);
	return keyList;
}

ㆍ 연결 리스트의 Iterable을 반환하는 메서드이다.
ㆍ 연결 리스트의 처음부터 끝까지 순회하며, 키를 ArrayList에 추가한다.
ㆍ 마지막에는 연결 리스트의 모든 키가 추가된 ArrayList를 반환한다.

 

contains() 메서드

public boolean contains(K key) {
	return get(key) != null;
}

ㆍ get( ) 메서드의 반환 값을 판단하여 키의 포함 여부를 알아낸다.

 

isEmpty() 메서드

public boolean isEmpty() {
	return N == 0;
}

ㆍ 연결 리스트의 노드 개수를 판단하여 빈 연결 리스트인지 알아낸다.

 

size() 메서드

public int size() {
	return N;
}

ㆍ 연결 리스트의 노드 개수를 반환함으로써 연결 리스트의 크기를 알아낸다.

---

참고 문헌 및 자료

ㆍ R.Sedgewick and K. Wayne, Algorithms (4th Ed.), Addison-Wesley.

ㆍ E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, Silicon Press, 2nd Edition.

ㆍ https://algs4.cs.princeton.edu/31elementary/

---

GitHub - qlsdud0604/algorithm-study: 자료구조 및 알고리즘 공부 기록 공간