[CS] 4-2 자료구조. - 배열, 연결리스트, 스택 & 큐, 해시 테이블

"이것이 취업을 위한 컴퓨터 과학이다 with CS 기술면접" 책을 참고했습니다.

1. 배열 & 연결리스트

프로그래밍 언어를 기반으로 학습을 단 한 번이라도 해봤다면 익숙한 자료구조인 배열과 연결리스트다. 배열과 연결리스트는 상황에 따라서 다른 자료구조를 만드는 재료로도 활용되기 때문에 깊게 이해하는 것이 좋다. 차근차근 알아보자.

1-1 배열

배열(Array)이란 일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조를 의미한다. 각 요소에는 0부터 시작하는 고유한 순서 번호인 인덱스가 매겨지며, 이 인덱스를 기준으로 요소들을 식별할 수 있다. 다음과 같은 특징을 지닌다.

• 특정 요소 접근 시간은 요소의 개수와 무관하게 일정한 O(1)이다. 인덱스만 찾아서 조회하면 되기 때문.
• 앞에서부터 차례대로 특정 요소를 찾아나간다면 연산 시간은 O(N)이다. N개의 요소를 차례대로 탐색하기 때문.
• 특정 요소를 추가, 삭제, 수정하는 경우에도 시간 복잡도는 O(N)이다. 중간에 추가되거나 삭제되는 요소로 인해 이후 요소들이 이동해야 되기 때문.
• 배열은 크기가 고정되었는지 아닌지에 따라서 정적 배열과 동적 배열로 나뉜다. 일반적으로 우리가 배열이라고 지칭할 때는 정적 배열을 의미하며 크기가 고정되어 있는 형태이다.

 

Java 코드에서 실제 배열을 선언하고 활용하는 방법을 예시로 보게 되면 다음과 같다.

public class Main {
    public static void main(String[] args) {
    // 다양한 선언 및 초기화
        int[] numList = new int[10];
        int[] numList2 = {1,2,3,4,5,6,7,8,9,10};
        int[] numList3 = new int[]{1,2,3,4,5,6,7,8,13,14};

	// 선언만 했을 경우 데이터 저장.
        for(int i = 0; i < numList.length; i++) {
            numList[i] = i;
        }

	// 각각 조회
        for(int i = 0; i < numList.length; i++) {
            System.out.println(numList[i]);
        }
    }

}

조금 역사가 오래된 C++, C, Java 같은 경우, 배열은 크기가 고정되어 있고, 배열 선언 시 받을 데이터 타입에 대해서 한 가지만 받을 수 있는 특징이 있다. 이는 메모리 관리의 효율성을 고려해 설계된 부분이며 위에서 설명하는 배열의 이론적인 부분과 가장 친숙하게 맞닿아 있는 부분이기도 하다. 

 

1-2 연결리스트

연결리스트는 노드의 모음으로 구성된 자료구조이다. 노드란 연결리스트의 구성 단위로, 저장하고자 하는 데이터와 다음 노드의 메모리 상의 주소 정보를 포함한다. 어느 노드에 접근한다면, 그 노드에 담긴 정보에 따라 그 다음 노드의 정보도 알 수 있고 이 과정이 순차적으로 반복적으로 이루어지게 된다. 이 점을 인지하고 연결리스트의 특징을 정리하면 다음과 같다.

• 연결리스트의 첫 번째 노드는 헤드, 마지막 노드는 꼬리(tail)라고 부른다.
• 배열과 달리 반드시 메모리에 순차적으로 저장되어 있을 필요가 없기 때문에, 연속적으로 구성되어 있는 데이터를 불연속적으로 저장할 때 유용하게 사용가능하다.
• 연결리스트는 특정 요소에 접근하려면 앞에서부터 순차적으로 노드를 찾아서 접근해야하므로, 탐색 시간은 O(N)이다.
• 노드의 위치만 바꾸면 되기 때문에 추가, 삭제가 매우 빠르다. 탐색 시간은 O(1)이다.
• 기본적으로 순차적으로 한 방향으로 헤드에서 꼬리 방향으로 이루어지는 연결리스트를 싱글 연결 리스트라고 한다.
• 싱글 연결 리스트는 다음 노드는 알 수 있지만, 이전 노드는 알기 어려운 단점이 있다.
• 싱글 연결 리스트를 보완하기 위해 나온 이중 연결 리스트는 한 노드에 이전 노드에 대한 정보도 포함하고 있다. 다만 그만큼 더 많은 저장 공간을 필요로 한다.
• 꼬리 노드가 헤드 노드를 가리켜 노드들이 원형으로 구성된 경우 환형 연결 리스트라고 부른다.

 

Java에서 실제 코드의 예시를 보면 다음과 같다.

import java.util.LinkedList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new LinkedList<>();

        list.add("hello");
        list.add("hello2");
        list.add("hello3");
        list.add(1,"hello1");

        for (String s : list) {
            System.out.println(s);
        }

        list.remove(0);
        list.remove("hello2");

    }

}

위와 같이 순차적으로 저장하거나, 특정 위치에 저장해 사용 가능하다.

---

2. 스택 & 큐

2-1 스택

스택은 한 쪽에서만 데이터의 삽입 삭제가 가능한 자료구조를 의미하며, 흔히 박스 쌓기나, 과자 통 같은 경우로 비유가 되며, 특징은 다음과 같다.

• 저장하는 연산은 push, 데이터를 빼내는 연산은 pop 이라고 한다.
• 스택은 후입선출(LIFO) 구조로 나중에 넣은 데이터가 가장 먼저 나오게 된다.
• 스택은 여러가지 경우에 사용 가능하지만, 가장 유용한 상황은 다음과 같다.
  • 최근에 임시 저장한 데이터를 가장 먼저 활용해야 할 때 많이 사용된다. 운영체제에서 스택 영역의 경우, 함수의 실행이 끝나면 더 이상 필요 없는 지역변수, 매개변수, 함수 복귀 정보 같은 함수 호출 정보는 사용이 끝나면 제일 먼저 삭제해야할 정보이므로 스택 구조는 유용하게 사용된다.
  • 뒤로가기 기능을 만들고 싶을 때 사용 가능하다. 예를 들어 웹 브라우저에서 뒤로가기 버튼의 경우, 스택에 차례대로 URL 주소를 저장해놨다가 뒤로 가기 버튼을 누르면 최근 주소를 빼내고 이전 주소로 찾아가면 된다.

스택의 경우 코드로 구현하면 다음과 같다.

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        
        // 스택에 값 추가 (push)
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Stack: " + stack);
        
        // 스택에서 값 꺼내기 (pop)
        System.out.println("Popped: " + stack.pop());
        System.out.println("Popped: " + stack.pop());
        
        System.out.println("Stack after pops: " + stack);
        
        // 스택의 최상단 값 확인 (peek)
        System.out.println("Peek: " + stack.peek());
    }
}

Stack: [10, 20, 30]
Popped: 30
Popped: 20
Stack after pops: [10]
Peek: 10

2-2 큐

스택과 달리 큐는 한쪽으로 데이터를 삽입하고, 다른 한 쪽으로 데이터를 삭제하는 자료구조이다. 비유를 들 때, 일종의 터널로 많이 비유하기도 한다. 특징은 다음과 같다.

• 큐는 데이터가 삽입되면(First In) 데이터가 가장 먼저 나오게 된다(First Out). 이런 점 때문에 큐를 선입선출(FIFO) 자료구조라고 이야기한다.
• 큐의 한 쪽 킅에 데이터를 삽입하는 연산을 enqueue, 데이터를 삭제하는 연산을 dequeue 라고 한다.
• 임시 저장된 데이터를 차례차례 가져와야 하는 각종의 Buffer로도 많이 활용된다. 즉 줄을 세워야하는 경우 많이 사용한다고 보면 된다.
• 큐는 다양한 형태로 변형되는데, 대표적으로 원형 큐, 덱, 우선순위 큐 등이 대표적이다.
  • 원형 큐 : 데이터를 삽입하는 쪽, 삭제하는 쪽을 하나로 연결해 원형으로 사용되는 구조
  • 덱(deque) : 양방향 큐(double-ended queue)의 약자로, 양쪽으로 데이터의 삽입 삭제가 가능한 구조
  • 우선순위 큐(priority queue) : 정해진 우선순위가 높은 순으로 처리되는 큐를 말하며, 추후 학습할 트리와 힙이라는 자료구조를 기반으로 구현된다.

큐의 경우 코드로 구현하면 다음과 같다.

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        
        // 큐에 값 추가 (offer) [enqueue]
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        System.out.println("Queue: " + queue);
        
        // 큐에서 값 꺼내기 (poll) [dequeue]
        System.out.println("Polled: " + queue.poll());
        System.out.println("Polled: " + queue.poll());
        
        System.out.println("Queue after polls: " + queue);
        
        // 큐의 첫 번째 값 확인 (peek)
        System.out.println("Peek: " + queue.peek());
    }
}

Queue: [10, 20, 30]
Polled: 10
Polled: 20
Queue after polls: [30]
Peek: 30

---

3. 해시 테이블

해시 테이블(hash table)은 키(key)와 값(value)의 쌍으로 이루어진 표와 같은 형태의 자료구조를 말한다. 키는 해시 테이블에 대한 입력이고, 값은 키를 통해서 얻고자 하는 구체적인 데이터를 의미한다. 현실에서는 전화번호부라던지, 도서관의 도서 고유 번호라던지 다양한 방면에서 활용되고 있다. 해시 테이블의 특징은 다음과 같다.

• 데이터는 버킷(bucket)에 저장되어 있다. 버킷은 여러 개 존재하며, 여러 버킷들은 배열을 형성한다.
• 해시 함수는 키를 인자로 활용해서 버킷 배열의 인덱스를 반환하여 원하는 곳에 접근할 수 있게 만들어준다.
• 해시 함수의 연산 방법을 해시 알고리즘이라고 하는데, 대표적으로 MD5, SHA-1, SHA-256, SHA-512, SHA3 등이 있다.
• 같은 데이터라 하더라도 알고리즘이 달라지면 도출되는 해시 값이 달라진다.
• 해시 테이블을 사용하는 가장 큰 이유는 key를 활용한 빠른 검색 속도이다. 일반적인 상황에서 해시 테이블은 검색, 삽입, 삭제 연산의 경우 시간 복잡도는 O(1) 이다.
• 다만 속도가 빠른 만큼, 많은 메모리 공간을 소모한다.
• 서로 다른 키에 대해서 같은 해시 값이 나오는 경우를 해시 충돌이라고 하는데, 이를 해결하기 위한 방법으로 체이닝과 개방 주소법이 있다.
  • 체이닝 : 충돌이 발생한 데이터를 연결 리스트로 추가하는 방법으로, 단순하게 해결할 수 있지만, 충돌의 양이 많아질 경우 속도가 느려져 해시 테이블의 장점이 빛이 바랠 수 있다.
  • 개방 주소법 : 충돌 발생 시 , 충돌이 발생한 버킷의 인덱스가 아닌 다른 인덱스에 데이터를 저장하는 방법이다.
    • 충돌 발생 시 비어 있는 다른 버킷의 인덱스를 찾는 과정을 조사(probe)한다고 표현한다.
    • 조사 방법에 따라 선형 조사법, 이차 조사법 등으로 나뉜다.
  • 이중 해싱 : 2개의 해시 함수를 사용하는 방법으로, 충돌 발생 시 나머지 해시 함수에 대한 해시 값만큼 떨어진 거리에 위치한 인덱스를 찾는 방식이다.

자바에서 해시 테이블을 구현하는 방법은 크게 HashTable과 HashMap이 있는데, HashTable은 동기화를 고려해 성능이 조금 떨어지고, HashMap의 경우 동기화를 고려하지 않아 속도가 상대적으로 더 빠르다. 코드는 아래와 같다.

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // HashMap 생성
        HashMap<String, Integer> hashMap = new HashMap<>();
        
        // 값 추가 (put)
        hashMap.put("Apple", 3);
        hashMap.put("Banana", 5);
        hashMap.put("Orange", 2);

        // 값 출력
        System.out.println("HashMap: " + hashMap);
        
        // 특정 키의 값 가져오기 (get)
        int appleCount = hashMap.get("Apple");
        System.out.println("Apple count: " + appleCount);
        
        // 특정 키의 값 업데이트
        hashMap.put("Apple", 4);
        System.out.println("Updated HashMap: " + hashMap);
        
        // 특정 키의 존재 여부 확인 (containsKey)
        if (hashMap.containsKey("Banana")) {
            System.out.println("Banana is available.");
        }
        
        // 모든 키와 값 출력 (entrySet)
        for (var entry : hashMap.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
        
        // 값 삭제 (remove)
        hashMap.remove("Orange");
        System.out.println("After removing Orange: " + hashMap);
    }
}

HashMap: {Apple=3, Banana=5, Orange=2}
Apple count: 3
Updated HashMap: {Apple=4, Banana=5, Orange=2}
Banana is available.
Key: Apple, Value: 4
Key: Banana, Value: 5
Key: Orange, Value: 2
After removing Orange: {Apple=4, Banana=5}

---

여기까지 여러 자료구조에 대해서 간단하게 알아봤다. 다만 이론적인 내용이다보니 조금 간단하게 적고 실제 코드로 적용하는 부분 위주로 작성했다.. 다음 시간에는 이번에 못다룬 트리와 그래프에 대해서 다룰 예정이다.

---

참고

[CS - 자료구조] 해시 테이블 (Hash Table) 개념 정리