🐢 2. Data Structures

💡 자료구조

• 배열

• 링크드 리스트

• 스택

• 큐

• 해시 테이블

---

🫧 배열과 문자열

❤️ 해시테이블 (hash table)

효율적인 탐색을 위한 자료구조로서, key를 value 에 대응시킴

최악의 경우 O(n) // n은 키의 개수

최선의 경우 O(1)

1) 키의 해시 코드 계산

• 키의 자료형은 보통 int or long
• 키의 개수 무한 (int 는 유한)

2) hash(key) % array_length 방식으로 해시 코드 이용해 배열의 인덱스 구함

• 서로 다른 두 개의 해시 코드가 같은 인덱스 가리킬 수 있음

3) 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트 존재

• 키와 값을 해당 인덱스에 저장 (반드시 연결리스트 이용!)
• 💥 충돌 : 서로 다른 두 개의 키가 같은 코드를 가리키거나, 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우

⇒ 키에 상응하기 위해서 위를 반복!

⇒ 주어진 키로부터 해시 코드를 계산, 해시 코드를 이용해 인덱스 계산, 해당 키에 상응하는 값을 연결 리스트에서 탐색

➕ 균형 이진 탐색 트리 (balanced binary search tree) 
: 탐색 시간은 O(logN)
: 크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 적은 공간 사용 가능
: 키의 집합을 특정 순서대로 접근 가능

❤️ ArrayList 와 가변 크기 배열

• ArrayList
  • 동적 가변 크기 기능 내재의 배열일 때 사용
  • 필요에 따라 크기를 변화 가능
  • O(1)의 접근 시간을 유지
  • 배열이 가득 차면, 배열의 크기를 두 배로 늘림
    • O(n)으로 늘려지지만, 상환 입력 시간으로 인해 O(1)
    • n개의 원소를 삽입할 때 소요 작업은 O(n)
    • 평균적으로 각 삽입은 O(1)

❤️ StringBuilder

가변 크기 배열을 이용해서 필요한 경우에만 문자열 복사

String joinWords(String[] words) {
  StringBuilder sentence = new StringBuilder();
  for (String w : words) {
      sentence.append(w);
  }
  return sentence.toString();
}

🫧 벡터 구현하기

➡️ size() - 항목의 개수

public static void main(String[] args){
    ArrayList<Object> sizeTest = new ArrayList<Object>();
    System.out.println( sizeTest.size() );  // 0
}

➡️ capacity() - 들어갈 수 있는 항목의 최대 개수

public static void main(String[] args) {
    StringBuffer buff = new StringBuffer(20);
    buff.append("GwangJik");
    System.out.println("Capacity : " + buff.capacity());    // 20
}

➡️ is_empty()

String test = null;
if(test != null && test.isEmpty()) {
    System.out.println(test);
}

➡️ at(index) - 인덱스에 있는 항목을 돌려주고, 인덱스가 범위 밖이면 에러를 냄

int digitStr = "456";

// 0번째에 있는 char 값을 리턴
digitStr.charAt(0) // 4

➡️ push(item)

var fruit = ["사과", "배", "포도"];
fruit.push("딸기");      // 배열 뒤쪽에 데이터 삽입 ["사과", "배", "포도", "딸기"]

➡️ insert(index, item) - index에 item을 삽입하고 기존 인덱스의 값부터 쭉 오른쪽으로 쉬프트

public class ArrayListDemo {
    public static void main(String[] args)
    {
        // create an empty list with an initial
        // capacity
        List<String> list = new ArrayList<String>(5);
 
        // use add() method to initially
        // add elements in the list
        list.add("Geeks");
        list.add("For");
        list.add("Geeks");
       
        // Add a new element at index 0
        list.add(0, "Hello");
       
        // prints all the elements available in list
        for (String str : list) {
            System.out.print(str + " ");
        }
    }
}
// Hello Geeks For Geeks

➡️ prepend(item) - 맨 앞에 원소를 삽입

int[] arr = { 10, 20, 30 };

arr = ArrayUtils.add(arr, 40);

➡️ pop() - 마지막 원소를 삭제하고 값을 돌려준다

var fruit = ["사과", "배", "포도"];
fruit.pop();             // 배열 뒤쪽의 데이터 제거 ["사과", "배"]

➡️ delete(index) - delete item at index, shifting all trailing elements left

import java.io.File;  // Import the File class

public class DeleteFile {
  public static void main(String[] args) { 
    File myObj = new File("filename.txt"); 
    if (myObj.delete()) { 
      System.out.println("Deleted the file: " + myObj.getName());
    } else {
      System.out.println("Failed to delete the file.");
    } 
  } 
}

// Deleted the file: filename.txt

➡️ remove(item) - looks for value and removes index holding it (even if in multiple places)

String[] fruitsArray = {"apple", "banana", "kiwi", "mango"};
ArrayList<String>  fruits = new ArrayList<>(Arrays.asList(fruitsArray));
System.out.println("all: " + fruits.toString());

String returned = fruits.remove(2);
System.out.println("remove(2): " + fruits.toString());
System.out.println("returned: " + returned);

// all: [apple, banana, kiwi, mango]
// remove(2): [apple, banana, mango]
// returned: kiwi

➡️ find(item) - looks for value and returns first index with that value, -1 if not found

import java.util.regex.Matcher;  
import java.util.regex.Pattern;  
  
public class BooleanFindMethodExample1 {  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
        Pattern p=Pattern.compile("java");  
        Matcher m=p.matcher("HellojavaHellojava");  
        int c=0;  
        // finding matching char   
        while(m.find())  
        {  
        c=c+1;  
        System.out.println("Start position of matching String "+m.start());  
        System.out.println("End position of Matching String (java) "+m.end());  
        }  
        System.out.println(" Number of matches : "+c);  
    }  
}

Pattern pat = Pattern.compile("여기에 정규식 입력"); 
패턴을 정의 한 후

Matcher match = pat.matcher("여기에 조사할 문자열");
정의된 패턴에 매치 되는 값을 저장한다.

match.find()
매치된 값이 있으면 true 없으면 false를 반환한다.

match.group()
매치된 값을 반환한다.

➡️ resize(new_capacity) // private 함수

• 용량이 꽉 차면, 그 두배로 크기를 조정한다.
• item을 하나 꺼낼 때, 용량이 1/4이라면, 용량을 절반으로 줄인다.

🫧 연결 리스트

: 차례로 연결된 노드를 표현해주는 자료구조

단) 배열과 달리 특정 인덱스를 상수 시간에 접근할 수 없다

(k번째 원소를 찾고싶다면 처음부터 k번 루프 돌아야함)

장) 리스트의 시작 지점에서 아이템을 추가하거나 삭제 연산을 상수 시간에 할 수 있다

• 단방향

  

  • 각 노드는 다음 노드 가리킴

• 양방향

  

  • 각 노드는 다음 노드와 이전 노드를 함께 가리킴

💖 (단방향) 연결 리스트 만들기

class Node {
	Node next = null;
	int data;
	public Node(int d) {
		data = d;
	}

	void appendToTail(int d) {
		Node end = new Node(d);
		Node n = this;
		while (n.next != null) {
			n = n.next;
		{
		n.next = end;
	}
}

💖 (단방향) 연결 리스트 삭제

1) 노드 n 이 주어지면, 이전 노드 prev 를 찾아 prev.next 와 n.next 가 같도록 설정한다

• 양방향 연결 리스트일 경우, n.next가 가리키는 노드를 갱신하여 n.next.prev 가 n.prev 가 같도록 설정

💥 주의

• 널 포인트 검사를 반드시 한다
• head와 tail 포인터를 갱신한다

Node deleteNode(Node head, int d) {
	Node n = head;
	if (n.data == d) {
		return head.next;    // head 움직이기
	}

	while (n.next != null) {
		if (n.next.data == d) {
			n.next = n.next.next;
			return head;     // head 움직이지 않음
		}
	}
	return head;
}
	

💖 Runner (부가 포인터)

연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것

한 포인터가 다른 포인터보다 앞서도록 한다

• 앞선 포인터는 뒤 포인터보다 항상 지정된 개수만큼은 앞설 수 있다
• 뒤 포인터를 여러 노드를 한번에 뛰어넘도록 설정할 수 있다

💖 재귀 문제

재귀 호출 깊이가 n일 경우, 해당 재귀 알고리즘이 적어도 O(n) 의 공간을 사용

🫧 링크드 리스트 구현하기

➡️ size() - 리스트 안의 데이터 개수를 반환한다.

LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.size()); //list 크기 : 3

➡️ empty() - 리스트가 비어있다면 true를 반환한다.

// 리스트가 비었는가
template <typename E>
bool SLinkedList<E>::empty() const{
    return head == NULL;
}

➡️ value_at(index) - index번째 위치의 value을 반환한다. (가장 앞은 0부터 시작한다.)

# declaring array
a = [18, 22, 33, nil, 5, 6]

puts "values_at() method form : #{a.values_at(2, 4)}\n\n"
// values_at() method form : [33, 5]

➡️ push_front(value) - 가장 앞에 value를 추가한다.

int main(void) {
	list<int> L = { 3, 7 };
	L.push_front(1); // { 1, 3, 7 }
	return 0;
}

➡️ pop_front() - 가장 앞에 있는 것을 제거하고, 그 value를 반환한다.

int main(void) {
	list<int> L = { 1, 5, 3, 7, 10 }   
	L.pop_front(); // { 5, 3, 7, 10 }
	return 0;
}

➡️ push_back(value) - 가장 끝에 value을 추가한다.

int main(void) {
	list<int> L = { 3, 7 };
	L.push_back(10); // { 3, 7, 10 }
	return 0;
}

➡️ pop_back() - 가장 끝에 있는 것을 제거하고, 그 value를 반환한다.

int main(void) {
	list<int> L = { 1, 5, 3, 7, 10 }   
	L.pop_back(); // { 5, 3, 7, 10}
	return 0;
}

➡️ front() - 가장 앞에 있는 것의 value를 가져온다.

class CircleList{
public:
    CircleList(); // 생성자
    ~CircleList(); // 소멸자

    const string& front() const; // 커서 다음의 원소
};

➡️ back() - 가장 끝에 있는 것의 value를 가져온다.

class CircleList{
public:
    CircleList(); // 생성자
    ~CircleList(); // 소멸자

    const string& back() const; // 커서의 원소

};

➡️ insert(index, value) - index번째 위치에 value를 추가한다. 즉, index번째에 새로 추가된 것이 기존의 index번째에 있던 것을 가리킨다.

list<int>::iterator iterInsertPos = list1.begin();
list1.insert(iterInsertsPos, 100);    // 첫 번째 위치에 100 넣기

➡️ erase(index) - index번째에 있는 노드를 삭제한다.

list1.erase(list1.begin());    // list1 첫 번 째 요소 삭제

➡️ value_n_from_end(n) - 뒤에서부터 n번째에 있는 노드의 value를 반환한다.

➡️ reverse() - 리스트를 뒤집는다.

public class UnitTest {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);

        System.out.println(list);
        list.reverse();

        System.out.println(list);
    }
}

// 1 -> 2 -> 3 -> 4
// 4 -> 3 -> 2 -> 1

➡️ remove_value(value) - value와 같은 값을 가지는 첫 번째 노드를 제거한다.

🫧 스택

: 데이터를 쌓아 올린다

LIFO (Last In First Out) 에 따라 자료를 배열한다

가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목

배열과 달리 스택은 상수 시간에 i 번째 항목에 접근할 수 없음

스택에서 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다

🫧 스택이 유용할 경우

: 재귀 알고리즘을 사용할 때 유용함

재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어 주고, 재귀 함수를 빠져 나와 퇴각 검색(backtrack) 할 때는 스택에 넣어 주었던 임시 데이터를 빼 줘야 한다

일련의 행위를 직관적으로 가능하게 해 준다

재귀 알고리즘을 반복적 형태 (iterative) 를 통해서 구현할 수 있게 함

🫧 스택 구현하기

function Stack(arr = Array()) {
  this.arr = arr;
}

let stk = new Stack();
let stk2 = new Stack(['test', 'test2']);

➡️ isEmpty() : 비어있는지 확인(반환값 t/f)

Stack.prototype.isEmpty = function(){
  return this.arr.length === 0;
}

➡️ push(data) : 스택에 데이터 추가하기

Stack.prototype.push = function (data) {
  this.arr.push(data);
};

➡️ pop() : 스택 맨 위의 데이터 삭제하기

Stack.prototype.pop = function () {
  return this.arr.pop();
};

➡️ top() : 스택 맨 위의 데이터 확인하기

Stack.prototype.top = function () {
  return this.arr.slice(-1);
};

➡️ size() : 스택의 데이터 개수 출력

Stack.prototype.size = function () {
  return this.arr.length;
};

🫧 큐

: FIFO (First In First Out) 순서

큐에 저장되는 항목들은 큐에 추가되는 순서대로 제거된다

• 너비 우선 탐색 (bfs)
  • 처리해야 할 노드의 리스트를 저장하는 용도로 큐 사용
  • 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장
  • 노드를 접근한 순서대로 처리 가능
• 캐시 구현

🫧 큐 구현하기

💖 tail 포인터가 있는 연결 리스트를 사용하여 구현하기

➡️ enqueue(value) - tail이 가리키는 곳에 value를 추가한다

int main()
{
    int keys[] = { 1, 2, 3, 4, 5 };
    Queue q;
 
    // 위의 키 삽입
    for (int key: keys) {
        q.enqueue(key);
    }
    return 0;
}

➡️ dequeue() - value를 반환하고 가장 최근에 추가된 원소(front)를 제거한다.

int main()
{
    int keys[] = { 1, 2, 3, 4, 5 };
    Queue q;
 
    // 위의 키 삽입
    for (int key: keys) {
        q.enqueue(key);
    }
 
    cout << q.dequeue() << endl;    // 1을 출력
    cout << q.dequeue() << endl;    // 2를 출력
 
    return 0;
}

➡️ empty()

#include <iostream>
#include <stack>
#include <cstdlib>
using namespace std;
 
// 두 개의 Stack을 사용하여 Queue 구현
class Queue
{
    stack<int> s1, s2;
 
public:
    // Queue에 아이템 추가
    void enqueue(int data)
    {
        // 첫 번째 Stack의 모든 요소를 두 번째 Stack으로 이동
        while (!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
 
        // 항목을 첫 번째 Stack에 푸시
        s1.push(data);
 
        // 모든 요소를 두 번째 Stack에서 첫 번째 Stack으로 다시 이동합니다.
        while (!s2.empty())
        {
            s1.push(s2.top());
            s2.pop();
        }
    }
 
    // Queue에서 아이템 제거
    int dequeue()
    {
        // 첫 번째 Stack이 비어 있는 경우
        if (s1.empty())
        {
            cout << "Underflow!!";
            exit(0);
        }
 
        // 첫 번째 Stack의 최상위 항목을 반환합니다.
        int top = s1.top();
        s1.pop();
        return top;
    }
};

🧡 고정 길이 배열을 사용하여 구현하기

• enqueue(value) - 사용 가능한 저장 공간의 끝에 item을 추가한다.
• dequeue() - value를 반환하고 가장 최근에 추가된 원소를 제거한다.
• empty()
• full()

💛 비용

• a bad implementation using linked list where you enqueue at head and dequeue at tail would be O(n) because you’d need the next to last element, causing a full traversal each dequeue
• enqueue: O(1) (amortized, linked list and array [probing])
• dequeue: O(1) (linked list and array)
• empty: O(1) (linked list and array)

🫧 해시테이블 (hash table)

: 효율적인 탐색을 위한 자료구조로서, key를 value 에 대응시킴

최악의 경우 O(n) // n은 키의 개수

최선의 경우 O(1)

🫧 연결리스트와 해시 코드 함수로 구현

1) 키의 해시 코드 계산

• 키의 자료형은 보통 int or long
• 키의 개수 무한 (int 는 유한)

2) hash(key) % array_length 방식으로 해시 코드 이용해 배열의 인덱스 구함

• 서로 다른 두 개의 해시 코드가 같은 인덱스 가리킬 수 있음

3) 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트 존재

• 키와 값을 해당 인덱스에 저장 (반드시 연결리스트 이용!)
• 💥 충돌 : 서로 다른 두 개의 키가 같은 코드를 가리키거나, 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우

⇒ 키에 상응하기 위해서 위를 반복!

⇒ 주어진 키로부터 해시 코드를 계산, 해시 코드를 이용해 인덱스 계산, 해당 키에 상응하는 값을 연결 리스트에서 탐색

균형 이진 탐색 트리 (balanced binary search tree)

탐색 시간은 O(logN)

크기가 큰 배열을 미리 할당해 놓지 않아도 되기 때문에 적은 공간 사용 가능

: 키의 집합을 특정 순서대로 접근 가능

🫧 해시테이블 구현하기

Linear probing을 사용하여 배열로 구현해보기

class Node:
    def __init__(self, key, value, next):
        self.key = key
        self.value = value
        self.next = next

➡️ hash(k, m) - m은 해시 테이블의 크기

// map의 크기: map.size()
map.size // 4
map.length // undefined

➡️ add(key, value) - 키가 이미 존재한다면, 값을 갱신한다.

Hashtable ht = new Hashtable();
ht.Add("irina", "Irina SP");
ht.Add("tom", "Tom Cr");

if (ht.Contains("tom"))
{
    Console.WriteLine(ht["tom"]);
}

➡️ exists(key)

map에 해당 key의 value 존재 여부: has(key)
map.has(str); // true
map.has(obj); // true
map.has('none'); // falsemap의 크기: map.size()
map.size // 4
map.length // undefinedmap의 크기: map.size()
map.size // 4
map.length // undefined

➡️ get(key)

• Map 객체는 key-value로 이루어진 해시테이블
  • set(): key-value pair를 map에 삽입
  • get(): key값으로 value를 찾아 리턴
  • key에 들어갈 수 있는 자료형은 number, string, function, object, NaN 등이 가능

    let number = 0;
    let str = 'string';
    let obj = { a: 1 };
    let func = () => {
        console.log('func');
    };
      
    map.set(number, 4); //key에 number 가능
    map.set(str, 1); // key에 string 가능
    map.set(obj, 2); //key에 object 가능
    map.set(func, 3); // key에 함수 가능
    map.set(number, 0); // 덮어쓰기 가능
      
    console.log(map); // Map(4) {0 => 0, "string" => 1, {…} => 2, ƒunc => 3}
      
    map.get(str); // 1
    map.get(obj); // 2
    map.get('none'); // undefined  
    map.get({ a: 1 }); // undefined, obj !== { a: 1 }
  

➡️ remove(key)

using System;
using System.Collections;
public class SamplesHashtable
{

   public static void Main()
   {
      // Creates and initializes a new Hashtable.
      var myHT = new Hashtable();
      myHT.Add("1a", "The");
      myHT.Add("1b", "quick");

      // Removes the element with the key "3b".
      myHT.Remove("3b");

   }
}