🚩시작하기 앞서

좋은 코드를 짜기 위해서 어떤 것이 필요할까?

여러가지가 있겠지만 대표적인 것 중 하나가 알고리즘 설계이다. 실제 개발 시에 알고리즘은 굉장히 중요하다. 들어오는 입력이 많으면 많을수록 알고리즘의 성능차이는 두드러지게 나타나며 이는 곧 서비스의 품질과 속도 그리고 사용자 경험에 많은 영향을 끼친다.

그렇다면 어떻게 알고리즘을 설계해야 할까?

그것은 내가 개발하고자 하는 서비스의 성격에 따라 달라진다. 훌륭한 개발자가 되기 위해서는 개발하고자 하는 서비스의 성격과 요구사항에 따라 알맞은 알고리즘을 설계할 수 있어야 한다.

그렇다면 좋은 알고리즘을 설계하는 방법은 무엇인가?

대표적인 방법으로 시간복잡도, 공간복잡도를 고려한 알고리즘 설계이다. 그러나 이러한 시간복잡도, 공간복잡도를 고려한 알고리즘을 설계하기 위해선 알맞은 자료구조를 사용해야 한다. 각각의 자료구조는 (읽기, 탐색, 추가, 삭제에서) 장단점이 있기 때문에 이를 잘 파악해야 개발하고자 하는 운영서비스를 최적화된 방식으로 개발할 수 있다.

이 시리즈 에서는 순서대로 다음에 대해 다룬다.

• 자료구조의 물리적 구조에 대해 2가지로 소개하고 비교
• 2가지를 응용한 여러 자료구조 소개(선형, 비선형) 및 JAVA가 객체지향적으로 자료구조를 제공하는 방법 (Collection Framework)

---

🚦구조도

각 자료구조의 단위자료는 정수(int), 실수(float), 문자(char) 및 문자열(String)과 같은 기본 자료형이 될 수도 있지만, 클래스, 구조체, 배열과 같은 사용자 정의 자료형도 있다. JAVA에서 String은 기본자료형(Primitive type)은 아니다.

• 배열 : 동일한 자료형을 여러 개 모은 것
• 구조체 : 동일하거나 다른 자료형을 여러 개 모은 것
• 클래스 : 구조체에 메소드까지 포함

단순구조

단순구조(Simple Structure)는 T/F, 정수, 실수, 문자 및 문자열과 같이 컴퓨터가 기본적으로 제공하는 자료형을 사용하는 경우이다. 기본 자료형을 여러 개 모은 사용자 정의 자료형 또한 여기에 속한다. 대부분의 프로그램이 사용자 정의 자료형을 사용하여 만들어진다. 사용자 정의 자료형을 선언하는 방법은 배열, 구조체, 클래스가 대표적이다.

선형구조

선형구조(Linear Structure)는 데이터들이 일렬로 쭉 저장되어 있는 형태이다. 일렬로 저장하는 방식은 리스트와 각 데이터가 다음 데이터의 위치를 가지는 연결리스트의 두 가지 방식이 있다. 일렬로 쭉 저장되어 있는 데이터를 사용하는 방법은 리스트와 연결 리스트 외에 사용 방법에 따라 스택, 큐, 데크가 추가된다.

비선형구조

비선형구조(Non-Linear Structure)는 데이터가 트리 형태로 저장되어 있다고 생각하고 사용하는 자료구조 이다. 구조의 종류는 트리와 그래프가 있다. 트리와 그래프도 물리적으로 보면 리스트와 연결 리스트를 이용하여 구현한다. 다만, 사용 방법이 다르므로 별도로 분리하여 생각한다.

파일구조

파일구조(File Structure)는 다양한 자료구조의 데이터를 파일에 저장하는 방식입니다. 순차 파일(Sequence File), 색인 파일(Index File), 직접 파일(Direct File)의 세 가지 방식이 있다.

🍳자료구조 구현체의 내부적 모습

자료구조는 리스트와 연결 리스트 이 2가지 물리적 구조를 기반으로 다양한 사용법으로 구현되어 있다. 즉, 대부분의 자료구조의 내부적 모습은 사실 리스트 또는 연결 리스트 인 것이다.

필자가 말하는 물리적 구조라는 말은 컴퓨터가 물리적으로 메모리를 저장하는 방식을 뜻한다.
다른 자료구조는 이 2가지를 이용해서 구현한 것이다.

예를 들어, 스택이나 큐도 연결 리스트를 이용하여 구현한 것이다. 혹은 리스트를 이용해서 구현해도 된다. 다만 연결 리스트 방식을 사용하면 추가, 삽입, 삭제를 했을 때 전체 데이터의 변동이 없어 속도가 빠르므로, 보통은 연결 리스트를 사용해 스택이나 큐를 구현하는 것이다. 다음내용이 이해가 안된다면 아래내용을 읽어보자.

- 리스트(List)

리스트(List)형 자료구조는 연속적인 저장의 형태를 가지며, 대표적으로 두 가지가 있다.

• 배열 : 크기가 변하지 않는 리스트형 자료구조, 중간의 값을 지워도 빈칸으로 유지한다.

• 리스트 : 크기가 변하는 자료구조, 중간의 값을 지우면 뒤의 것이 앞으로 이동한다.

  -Java의 ArrayList는 리스트(List)로 구현되었다.

이러한 리스트(List)를 이용한 자료구조는 데이터를 읽어오고(read) 순차적인 저장(insert)에는 효율이 좋다. 메모리가 연속적으로 할당되기 때문에 다음과 같은 원리로 저장하고 읽어올 수 있다.

//배열로 설명
int arr[] = new int[3]{0, 1, 2};

데이터 주소값 = 처음주소값 + 인덱스번호 x 자료형의 크기
예를 들어 arr[2]를 호출했을 때 주소값을 구하는 공식은 1008 = 1000 + 2 x 4 (int는 4byte다)
따라서 다음과 같은 공식을 적용하기만 하면 되니 데이터 읽기(read)에는 O(1)의 시간복잡도를 가진다. 저장(insert)도 마찬가지로 O(1)의 시간을 가진다.

그러나 중간에 데이터를 삽입할 시에는 기존데이터를 하나씩 뒤로 밀어야하므로 이때는 효율이 떨어진다. 또한, 용량을 변경해야할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야하기 때문에 효율이 떨어진다는 단점을 가지고 있다.

따라서 맨 끝에 순차적으로 추가하는게 아닌 비순차적인 저장(insert)은 효율이 떨어진다. 따라서 배열을 쓰고자 한다면 처음 인스턴스를 생성할 때, 저장할 데이터의 개수를 잘 고려해 충분한 용량의 인스턴스를 생성하는 것이 좋다.

- 연결리스트(Linked List)

연결리스트(Linked List) 자료구조는 저장하는 각 데이터(기본 데이터, 배열, 구조체, 클래스)가 데이터 외에 다음과 이전의 데이터를 가리키는 정보를 가지고 있는 구조이다. 대표적으로 3가지 구조가 있다.

• 연결 리스트 : 저장된 각 데이터{(데이터) + (다음 데이터의 포인터)}로 이루어진 것으로, 한 방향으로만 탐색 가능한 구조
  

//연결 리스트
class Node {
	Node next; 		// 다음 요소의 주소를 저장
    Object obj; 	// 데이터를 저장

• 이중 연결 리스트(Doubly Linked List) : 저장된 각 데이터가{(이전 데이터의 포인터) + (데이터) + (다음 데이터의 포인터)} 로 이루어진 것으로, 양방향 탐색 가능 구조
  -이전요소 접근이 어려운 단방향 연결리스트의 단점을 보완
  

  //이중 연결 리스트
  class Node {
      Node next; 		// 다음 요소의 주소를 저장
      Node previous;	// 이전 요소의 주소를 저장
      Object obj; 		// 데이터를 저장

• 원형 연결 리스트(Circular Linked List) : 이중 연결 리스트의 양끝이 연결되어 있는 구조
  -이중 연결 리스트를 더욱 보완하여 접근성을 높임
  -Java의 LinkedList클래스는 원형 연결 리스트로 구현되었다
  

  //원형 연결 리스트
  class Node {
      Node next;   // 다음 요소의 주소를 저장 
                   // 맨 끝 노드는 맨 처음 노드의 주소를 저장
      Object obj;  // 데이터를 저장    
    

연결리스트(Linked List)는 배열의 단점을 보완하기 위해서 고안된 자료구조이다. 배열은 모든 데이터가 연속적으로 존재하지만 링크드 리스트(Linked List)는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어 있다.
위 그림에서 알 수 있듯이 링크드 리스트는 각 요소(node)들을 자신과 연결된 다음 요소에 대한 참조(주소값)으로 데이터가 구성되어 있다.

이렇게 구성한 연결리스트(Linked List)의 데이터 추가와 삭제는 매우 간단하다. 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠르다. 두 번의 참조변경으로 추가가 가능하다.

삭제의 경우 삭제하고자 하는 요소의 이전요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하기만 하면 되는 것이다. 이 또한 단 하나의 참조 변경으로 삭제가 이루어지니 매우 빠르다.

---

다음처럼 우리는 자료구조 구현체의 내부적 모습을 리스트와 연결리스트 2가지 물리적 형태로 알아보았다. 그렇다면 아까 말했던 이 내용을 이해할 수 있을 것이다.

스택이나 큐도 연결 리스트를 이용하여 구현한 것이다. 혹은 리스트를 이용해서 구현해도 된다. 다만 연결 리스트 방식을 사용하면 추가, 삽입, 삭제를 했을 때 전체 데이터의 변동이 없어 속도가 빠르므로, 보통은 연결 리스트를 사용해 스택이나 큐를 구현하는 것이다.

독자가 스택이나 큐의 개념을 알고있었다면 다음 내용을 이해할 수 있다. 스택이나 큐와 같이 자료의 추가, 삽입, 삭제가 빈번하게 일어나는 자료구조는 리스트가 아닌 연결리스트로 구현해야 전체 데이터의 변동이 적어 속도가 빠르다는 것이다.

ArrayList vs LinkedList

다음은 Java의 ArrayList와 LinkedList add(추가), 읽기(get;set;), 탐색(*indexof), 삭제(remove) 등의 실제 시간복잡도 이다. 앞에서 말했듯이 ArrayList는 리스트로 구현되어있고 LinkedList는 연결리스트로 구현이 되어있다.

리스트로 구현된 ArrayList는 순차적으로(끝에) 데이터를 추가, 삭제할 때는 O(1)의 시간복잡도가 들지만 비순차적인 데이터의 추가, 삭제는 O(n)의 시간복잡도를 가진다. 반면, 연결리스트로 구현된 LinkedList(단일 연결)의 데이터 추가, 삭제는 맨 앞의 추가 삭제를 제외하고는 일관적으로 O(n)의 시간복잡도를 가진다.

데이터를 읽는데에는(get;set;) ArrayList는 항상 O(1)의 시간복잡도가 걸리는 반면 LinkedList(단일 연결)는 최악의 경우 모든 노드를 전부 확인할 수 있으므로 O(n)의 시간복잡도를 가진다.

여기서 주의할 점이 있는데 언급했듯이 Java에서 LinkedList 구현클래스는 원형 연결 리스트(Circular Linked List)로 구현이 되어있다. 그래서 실제로는 add(끝)이나 remove(끝)을 추가하는 경우에도 단일 연결 리스트는 O(n)의 시간이 걸리는데 비해 원형 연결 리스트로 구현된 LinkedList는 O(1)의 시간이 걸린다.

정리
결국 ArrayList 클래스가 LinkedList 클래스에 비해 더 이점을 가지는 경우는 다음 2가지 이다.
1. get;set; (읽기,쓰기)
2. 용량이 변하지 않는다는 가정에서의 순차적 데이터추가

결론
데이터의 개수가 변하지 않는 경우라면 ArrayList가 최상의 선택이 되겠지만, 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택이 될 것이다.
또는 두 클래스를 적절히 사용하여 데이터를 읽거나 저장할 때는 ArrayList를 사용하고 데이터의 변경작업이 있을 때는 LinkedList로 데이터를 옮겨서 사용하면 좋은 효율을 얻을 수도 있을 것이다.

---

다음 2편에선 여러 자료구조를 쉽게 제공하는 Java Collection Framework를 알아보자.

References

• Java의 정석 (개정 3편) - 남궁성
• (그림으로 정리한) 알고리즘과 자료구조 - 조민호
• 자바로 배우는 핵심 자료구조와 알고리즘 - Downey, Allen