Data Structure (자료구조)

비전공자는 도전해볼 수 있고, 전공자는 쉽게 배울 수 있는 데이터 스트럭쳐 수업

Data Structure (자료구조) 비전공자는 도전해볼 수 있고, 전공자는 쉽게 배울 수 있는 데이터 스트럭쳐 수업

리스트 (List)

배열은 다수의 데이터를 그룹핑해서 효율적으로 관리할 수 있는 데이터 스트럭쳐입니다. 배열의 가장 큰 특징은 인덱스가 있다는 것입니다. 만약 인덱스를 알고 있다면 인덱스를 이용해서 데이터를 가져올 수 있습니다. 인덱스를 이용한 데이터의 조회는 매우 빠르게 처리 됩니다. 하지만 인덱스를 이용해서 데이터를 가져오려면 데이터에 대한 인덱스의 값이 고정되어야 합니다. 자연스럽게 어떤 엘리먼트가 삭제되면 삭제된 상태를 빈 공간으로 남겨둬야 합니다. 이것은 메모리의 낭비를 초래합니다. 또한 배열에 데이터가 있는지 없는지를 체크하는 로직이 필요하다는 의미이기도 합니다.

리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재라는 장점을 취한 데이터 스트럭쳐라고 할 수 있습니다.

삭제

아래와 같은 데이터가 있습니다. 4번째 엘리먼트인 40을 리스트에서 제외시키면 어떻게 해야 할까요?

배열이라면 아래와 같이 40이 없어진 자리가 빈자리로 남아 있을 것입니다. 덕분에 50의 인덱스 값은 변하지 않았습니다. 즉 인덱스가 주민등록 번호처럼 변하지 않는 고유한 값으로 남아있게 되는 것이죠.

리스트를 이용하면 아래와 같이 됩니다.

즉 데이터 밀도를 촘촘하게 유지할 수 있게 됩니다. 하지만 50의 인덱스 값은 4에서 3으로 변경되었습니다. 즉 인덱스는 더 이상 식별자로 사용할 수 없습니다.

추가

데이터를 추가해볼까요? 아래와 같은 데이터가 있습니다.

배열에서 인덱스를 유지하면서 40의 자리에 50을 추가하면 아래와 같이 되겠죠.

50이 삭제되었습니다. 이게 원하는 것이라면 상관없지만, 30과 40의 사이에 50을 추가하려는 것이었다면 아래와 같이 해야 합니다. 이렇게 처리되는 것이 리스트 방식입니다.

리스트에서는 인덱스가 중요하지 않습니다. 리스트 데이터 스트럭쳐의 핵심은 엘리먼트들 간의 순서입니다. 그래서 리스트를 다른 말로는 시퀀스(sequence)라고도 부릅니다. 시퀀스는 순서라는 의미죠. 즉 순서가 있는 데이터의 모임이 리스트입니다.

리스트는 수학적으로는 유한수열(finite sequence)을 프로그래밍적으로 표현한 것입니다. 수열이 무엇인지 잘 모르셔도 됩니다. 하지만 리스트를 익히고 수학의 수열을 공부해보시면 재미있을 겁니다. 수학을 잘하면 프로그래밍을 하는데 큰 도움이 됩니다. 하지만 프로그래밍을 해보고 수학을 공부하면 수학이 왜 해야 하는지 알 수 있습니다. 꼭 수학이 프로그래밍의 선행이 되어야 하는 것은 아닙니다. 혹시 수학에 무지하다고 겁먹지 않으셔도 됩니다.

리스트의 기능

리스트의 핵심적인 개념은 순서가 있는 엘리먼트의 모임이라는 것입니다. 빈 엘리먼트는 허용되지 않는다는 것도 기억해야 할 것입니다. 그리고 중복된 데이터를 허용한다는 것도 기억해두세요. 중복 허용은 배열과 리스트의 차이가 아닙니다. 배열도 중복이 허용됩니다. 중복 허용은 이후에 배울 set과 같은 데이터 스트럭쳐와의 차이라고 할 수 있습니다.

조금 이야기를 구체화합시다. 일반적으로 리스트 데이터 스트럭쳐는 아래와 같은 기능(operation)을 가지고 있습니다.

  • 처음, 끝, 중간에 엘리먼트를 추가/삭제하는 기능
  • 리스트에 데이터가 있는지를 체크하는 기능
  • 리스트의 모든 데이터에 접근할 수 있는 기능

위와 같은 기능을 가지고 있고, 순서가 있으면서 중복이 허용된다면 그러한 데이터 스트럭쳐를 리스트라고 합니다.

내장된 리스트

리스트를 직접 구현하는 것도 좋지만, 자신이 사용하고 있는 언어에 이미 리스트가 내장되어 있다면 그것을 사용해야 합니다. 많은 사람에 의해서 검증되었을 것이고 속도도 빠르기 때문이죠. 그런데 모든 언어가 리스트를 내장하고 있는 것은 아닙니다. 리스트를 제공한다고 해도 그 방식이 언어별로 다릅니다. 여기서는 몇 가지 언어들을 비교하면서 리스트라는 것에 대한 이해의 폭을 넓히는 시간을 갖도록 하겠습니다.

꽤 오래된 언어인 C에는 배열은 있지만 리스트가 없습니다. 리스트가 필요하다면 직접 구현해서 사용하곤 했지요. 아마도 여러분이 C를 사용하는 개발자라면 리스트를 구현하는 방법은 필수적인 것이었을 겁니다.

비교적 최근에 등장한 언어의 창시자들은 리스트의 중요함을 알고 있었습니다. 이들은 리스트를 기본적으로 지원해서 개발자들의 고충을 덜어주자는 생각을 했습니다.  이제는 많은 언어들이 리스트를 다양한 방식으로 지원하고 있습니다.

자바스크립트의 경우는 배열에 리스트의 기능을 포함하고 있습니다. 아래는 인덱스 3인 엘리먼트를 삭제하는 코드입니다.

numbers = [10, 20, 30, 40, 50];
//인덱스 3의 값을 제거
numbers.splice(3,1);
for(i = 0; i < numbers.length; i++){
console.log(numbers[i]);
}

실행결과는 아래와 같습니다.

10
20
30
50

(실행 : http://ideone.com/bO95Lp)

위의 코드에서 중요한 부분은 아래입니다.

numbers.splice(3,1);

splice는 배열 student의 3번째 인덱스의 엘리먼트를 삭제합니다. 삭제된 엘리먼트가 있던 자리는 뒤의 엘리먼트에 의해서 채워집니다.

즉 자바스크립트의 배열은 리스트의 기능도 포함하고 있는 것이라고 할 수 있습니다. 만약 각각의 엘리먼트가 고유한 인덱스를 가지고 있게 하려면 splice 대신에 numbers[3] = null; 과 같은 방법을 사용하면 됩니다. 즉 배열을 어떻게 이용하느냐에 따라서 배열이 될 수도 있고 리스트가 될 수도 있습니다. 프로그래머가 선택을 하면 됩니다.

파이썬은 자바스크립트와 비슷한 방법으로 리스트를 지원합니다. 그런데 파이썬에는 배열은 없고 리스트만 있습니다. 동일한 코드를 파이썬으로 작성해봅시다. 기능은 자바스크립트의 배열과 거의 같지만 이름이 리스트인 것이죠. 코드를 봅시다.

numbers = [10, 20, 30, 40, 50];
numbers.pop(3);
for number in numbers:
    print(number);

(실행 : http://ideone.com/R1gXG1)

실행결과는 자바스크립트와 같습니다.

자바스크립트나 파이썬과 같은 언어를 스크립트 언어라고 부릅니다. 이런 언어들이 추구하는 가치는 '쉽다' 입니다. 개발자들이 자주 사용하는 기능인 리스트를 언어에 포함해서 쉽게 사용할 수 있도록 배려하고 있는 것이죠.

리스트에 대한 효용은 어떤 언어를 사용하느냐에 따라서 달라집니다. 특히 많은 언어가 리스트를 기본적으로 지원하기 때문에 리스트를 직접 구현하는 경우는 줄고 있습니다. 그렇다면 리스트에 대한 공부는 이제 필요 없는 것일까요? 결론적으로 말씀드리면 그렇지 않습니다. 파이썬과 비슷한 시기에 나온 언어인 자바를 통해서 그 이유를 생각해 봅시다.

자바에서의 리스트

자바의 경우 배열과 리스트를 모두 개별적으로 지원합니다. 아래는 자바에서 배열을 사용한 예제입니다.

int[] numbers = {10,20,30,40,50};

String[]은 변수 numbers가 문자열을 엘리먼트로 하는 배열임을 의미합니다. 자바에서 배열의 원소를 제거하는 것은 쉬운 일이 아닙니다. 자바스크립트의 splice 파이썬의 pop 같은 기능을 제공하지 않기 때문입니다. 직접 구현해야 합니다.

대신 자바에서는 리스트라는 이름의 데이터 스트럭쳐를 지원합니다.

ArrayList numbers = new ArrayList();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
numbers.add(50);
numbers.remove(3);
System.out.println(numbers);

(실행 : http://ideone.com/XqCatU)

자세히 보시면 이름이 ArrayList 입니다. 왜 이런 이름이 있을까요? 코드를 조금 바꿔보겠습니다.

LinkedList numbers = new LinkedList();
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
numbers.add(50);
numbers.remove(3);
System.out.println(numbers);

(실행 : http://ideone.com/jTL3T4)

두 코드의 결과는 아래처럼 같습니다.

[10, 20, 30, 50]

두 개의 코드 사이의 차이는 무엇일까요? 첫 줄에서 아래와 같이 다른 코드가 사용되고 있습니다.

ArrayList와 LinkedList 사이의 공통점은 무엇일까요? 둘 다 List라는 것입니다. 차이는 Array와 Linked입니다. ArrayList나 LinkedList는 사용법이 거의 같습니다. 실행결과도 같습니다. 하지만 내부적인 구현방법이 다릅니다.

이것은 LCD와 CRT 모니터가 동작 방법은 많이 다르지만, 컴퓨터 입장에서는 완전히 똑같은 모니터인 것과 비슷한 이치라고 할 수 있습니다.

그럼 자바는 왜 ArrayList와 LinkedList를 동시에 제공하고 있을까요? 또 리스트도 제공하고 배열도 제공하는 이유는 무엇일까요?

(출처 : http://www.smashingmagazine.com/2010/06/06/designing-the-world-of-programming-infographic/)

위의 그림을 보시면 아시겠지만 자바는 파이썬이나 자바스크립트처럼 C 이후에 등장한 언어입니다. 그런데 자바는 스크립트 언어들과는 다른 길을 갑니다. 스크립트 언어의 핵심 미덕은 '쉽다' 입니다. 배열과 리스트를 지원하면서도 사용자들이 기억해야 할 것을 줄이기 위해서 둘을 융합하는 선택을 했습니다.

하지만 자바는 개발자가 배열과 리스트 중에 자신의 상황에 맞는 선택을 분명하게 선택할 수 있도록 이것들을 별도의 기능으로 지원하고 있습니다.

그렇다면 자바에서 하나의 리스트를 지원하지 않고 LinkedList와 ArrayList를 둘 다 지원하는 이유는 무엇일까요? 이것을 이해하기 위해서는 LinkedList와 ArrayList의 구현방법을 이해해야 합니다. 결론적으로 말하자면 인덱스를 이용해서 데이터를 가져오는 것이 빈번하다면 ArrayList가 훨씬 빠릅니다. 하지만 데이터의 추가/삭제가 빈번하다면 LinkedList가 훨씬 효과적입니다.

처리하고자 하는 데이터에 따라서 어떤 데이터 스트럭쳐를 선택할지를 잘 판단하는 것은 대규모 시스템을 구축하는데는 필수적인 능력입니다. 이러한 판단을 하기 위해서는 직접 데이터 스트럭쳐를 구현해서 사용하지 않더라도 내부적인 메커니즘을 이해할 필요가 있습니다.

무엇보다도 이후에 배우게 될 다양한 데이터 스트럭쳐가 리스트를 내부적으로 사용합니다. 따라서 리스트에 대한 충분한 이해는 매우 중요하다고 할 수 있습니다.

리스트가 무엇인지에 대한 이야기는 여기까지입니다. 후속 수업에서는 리스트를 구현하는 두가지 방법을 살펴보겠습니다.

댓글

댓글 본문
  1. 코딩이취미다
    자바 리스트
    LinkedList, ArrayList
  2. baeroro
  3. 이마누
    완료
  4. June
    설명 감사합니다! 이해가 명확히 되었어요 :)
  5. 설명 너무 좋아요~~~!!
  6. 머램이
    배열과 리스트의 차이를 잘 설명해주시다니 감사합니다!
  7. 김보라
    자바때부터 쭉 봐왔지만 정말 너무 좋아요ㅠㅠㅠㅠ저희 교수님이셨으면 좋겠어요ㅠㅠㅠ
  8. dmdanbi@nate.com
    감사합니다! 정리를 잘 해주셔서 이해가 아주 쏙쏙됩니다 :)
  9. SangHyeok Kim
    2017/03/30 수강완료!
    감사합니다!!
  10. egoing
    임지호님은 대단한 정리 기술을 가지셨네요~
    대화보기
    • 임지호
      List : 배열이 가지고 있는 인덱스로 값을 쉽게 찾을 수 있다는 장점 대신 배열에서의 단점을 보완해서 List 내부에 빈틈이 없게 만든, 값 간의 순서가 중요시 되는 자료구조이다.
      중간에 데이터를 추가하거나 삭제하면 배열에서는 빈자리가 그대로 남아있지만 List에서는 그 빈자리를 채우기 위해 뒤 데이터를 당기거나 밀어버린다.
      List의 핵심 컨셉은 순서유지와 중복허용이다.
      List를 많은 언어에서 지원하는데 그 방식이 다양하다.
      C는 지원하지 않고 자바스크립트와 파이썬은 배열과 List를 융합했고(개발자가 배열과 List에 대한 지식이 없어도 사용할 수 있도록) 자바는 배열과 List를 철저히 구분했다(개발자가 배열과 List에 대한 지식이 있어야 한다 더 나아가 List를 각각 장단점이 있는 2개의 List로 나누었다)
      이는 각 언어마다 추구하는 점이 다르다는 것을 시사하기도 하고 자료구조의 큰 핵심을 안다면 여러 언어에서 활용하기 좋다라는 의미도 되겠다
    • 자바비앙
      ArrayList는 추가/삭제가 느리고 LinkedList는 빠르다고 해서

      public static void main(String[] args) {

      //ArrayList arrList = new ArrayList();
      LinkedList linkList = new LinkedList();
      int i = 0;

      long start = System.currentTimeMillis();

      while(i <10000000){
      linkList.add(i);
      i++;
      }

      while(i<1){
      linkList.remove(i);
      i--;
      }

      long end = System.currentTimeMillis();

      System.out.println((end-start) /1000f);

      }

      이렇게 만들어서 속도를 비교해보았는데요 LinkedList가 더 느리네요.
      제가 잘못 비교한건가요?
    • 열공해용
      와 감사합니당!! 이고잉님 최고!!
    • 삼디
      리스트에 대해 자세히 알게되었네요 ^^
    • 떨스데이
      마지막 ArrayList와 LinkedList의 특징에 대한 이미지로 쉽게 이해할 수 있었습니다. 감사합니다.
    • 조문도석사가의
      정말 감사합니다~
    • urimago
      감사합니다 잘듣고 있어요
    • 임준용
      LinkedList가 저런 장점이 있었군요.
      좋은 공부하고 갑니다.
    • bepositive1223
      잘 듣고 있습니다~~

      너무 도움이 많이 되고 있어요~

      더 풍성한 내용으로 강의 준비 부탁합니다~~^^
    • 박대웅
      감사합니다. 잘 들었어요..^^
    • 김재영
      재밌게 잘 들었습니다. 언어에 대해서 잘 모르지만, 이렇게 설명을 들으니 이해가 잘 되네요.
    • david20jazz
      좋은 강의 감사합니다.
    • 장재원
      대박 내용이네요. 감사합니다!
    버전 관리
    egoing
    현재 버전
    선택 버전
    graphittie 자세히 보기