검색 (3) - 선형 검색 (Sequential Search, 리스트)

1. 알고리즘 개요

• 자료집합의 데이터를 순차적으로 탐색하는 방법

• loop를 돌려서 검색 데이터를 찾으면 반환하는 방식

 

2. 연산

• 삽입 : 자료집합 맨 뒤에 삽입 : O(N)

• 삭제 : 원소를 찾아서 지우고, 뒤의 원소들을 앞으로 당김 : O(N)

• 검색 : 원소를 찾아서 반환 : O(N)

3. 소스코드

class ListSeqMap<T> {
    private Node head = new Node();
    private int size;

    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }

        Node current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }

        return current.val;
    }

    public void add(T val) {
        if (head.val == null)
            head.val = val;

        else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }

            Node newNode = new Node();
            newNode.val = val;
            current.next = newNode;
        }

        this.size++;
    }

    public boolean remove(T val) {
        int removeIndex = -1, i = 0;
        for (Node node = head; node != null; node = node.next, i++) {
            if (node.val.equals(val)) {
                removeIndex = i;
            }
        }
        if (removeIndex != -1) {
            if (removeIndex == 0) {
                head = head.next;
            } else {
                Node beforeNode = head;
                for (int j = 0; j < removeIndex - 1; j++) {
                    beforeNode = beforeNode.next;
                }
                Node removeNode = beforeNode.next;
                beforeNode.next = removeNode.next;
            }
            
            this.size--;
            return true;
        }

        return false;
    }

    public int size() {
        return size;
    }

    public void print() {
        System.out.print("[");
        for (Node node = head; node != null; node = node.next) {
            System.out.print(node.val);

            if (node.next != null) {
                System.out.print(", ");
            }
        }
        System.out.print("]");
    }

    class Node {
        T val = null;
        Node next = null;
    }
}

 

4. 검색연산의 속도를 개선하는 방법

1) MRU (Most Recent Used) : 가장 최근에 사용한 데이터를 가장 앞으로 당겨서 놓는 기법으로, 자주 사용한 데이터일 수록 앞으로 쌓이게 되어 순차검색시 빠르게 데이터를 찾을 수 있게 됨.

 

 

5. Reference