리스트(list)에 대한 공부_기초

#틀린 부분이 있다면 언제든지 지적해주세요

 

42서울 본과정 중인데 과제하다가 리스트(list)에 대한 부분이 나와서 공부 겸 과제를 풀기 위한 사전 지식 습득을 해보기로 한다.

 

공부자료 출처 : https://opentutorials.org/module/1335/8634

데이터 스트럭쳐란 무엇인가? - Data Structure (자료구조)

 

---

자료구조(Data Structure)에 대해서 계속 들어오기는 했지만 (공부도 조금 했지만) 다 잊어버리기도 했고 왜 배워야하는지 다시 한번 상기시키고자 한번 정리하고 가기로 했다.

 

✅  자료구조(Data Structure)?

어릴 때 우리집에는 물건이 적었다. 미니멀 라이프를 지향하는건 아니고 집이 좁고 가난해서였다.

그러다가 입에 풀칠하고 조금 숨통이 트일 때부터 점점 물건이 늘어나기 시작했다. 김치냉장고, 옷장, 건조기(?) 등.

큰 물건은 찾기 쉽지만 작은 물건은 창고에 거의 던져놓았기 때문에 찾으려면 반나절은 걸린다.

처음에 (혹은 한번 시간을 내서) 많은 수납장과 박스를 사와 그 안에 물건들을 차곡차곡 정리해뒀다면 지옥 같은 창고가 되지 않았을 것이다.

 

자료구조가 필요한 이유도 그렇다.

물건이 많아질수록 잘 정리해놓아야 좀 더 빠르게 필요한 물건을 찾을 수 있는 것처럼 데이터도 잘 정리 정돈 되어 있으면 참 좋다.

그래서 정리하기 위한 구조물을 만드는데(마치 수납장처럼) 그 구조물을 데이터 스트럭쳐(Data Structure, 자료구조)라고 한다.

구조물이 영어로 Structure이니까 [자료 구조물]인건가..

 

프로그래밍 언어를 처음 배울 때 알게 되는 배열(array)도 대표적인 데이터 스트럭쳐라고 한다. (출처 : 위의 URL 참고)

 

데이터가 10개 정도 있으면 찾는데 오래 걸리지 않겠지만 100만개 이상이라면..

더구나 혼자 쓰는게 아니라 20명 정도의 동료들이 함께 쓰는 데이터라면..

구조물을 이용해 잘 정리해놓지 않으면 과거의 나와 동료들에게 김치 싸다귀(?)를 맞을지도 모른다.

(사실 자료구조가 필요한 이유는 메모리 효율적인 사용으로 프로그램의 속도 향상 등을 위해서이다)

 

✅  리스트(List)

다 배우면 참 좋겠지만 그건 나중에 잉여 시간이 생길 때 하기로 하고 당장 과제에 필요한 리스트를 공부해보자.

 

배열(array)은 데이터를 그룹핑해서 효율적으로 관리할 수 있는 좋은 데이터 스트럭쳐이라고 한다.

인덱스를 이용해서 데이터에 접근할 수 있어서 데이터 조회 시 매우 빠른 속도로 처리가 가능하다고 한다.

하지만 중간의 데이터 하나가 삭제되면 그 공간은 빈 공간으로 남겨두게 된다. (메모리 낭비)

 

이건 여러 귀찮은 상황을 연출하는데, 불필요한 메모리 사용으로 낭비가 되기도 하고

인덱스를 이용해서 데이터를 꺼내올 때 데이터(값)가 존재하는지 없는지 확인도 해줘야 한다.

 

리스트(list)는 이런 아쉬운 점을 메워준다.

이렇게 처리되는게 리스트 방식이라고 한다.

사실 리스트에서는 인덱스가 중요하지 않고, [순서]가 더 중요하다고 한다.

 

리스트는 이런 특징을 갖고 있다.

⚠️  리스트의 특징

- 순서가 있는 요소(엘리먼트)의 모임이다.

- 빈 요소(엘리먼트)는 허용하지 않는다.

- 중복된 데이터를 허용한다.

 

---

✅  리스트(List) 기능

그래서 리스트라는 데이터 스트럭쳐는 이런 기능들을 가지고 있다.

마치 printf라는 함수가 인자를 출력하는 기능을 하는 것처럼, 리스트라는 데이터 스트럭쳐도 이런 기능을 한다는 것이다.

 

* 처음, 중간, 끝에 엘리먼트를 추가하거나 삭제하는 기능

* 리스트에 데이터가 있는지 체크하는 기능

* 리스트의 모든 데이터에 접근할 수 있는 기능

 

리스트를 직접 구현하는 것도 좋지만, 내장된 리스트 기능을 사용하는 것도 좋다고한다.

예를 들어 자바스크립트는 [배열]에 리스트 기능을 포함하고 있다.

 

이 내용은 생활코딩을 읽어보면 좋을 것 같다.

42 과제에서는 리스트를 직접 구현해야하기 때문에 내장된 리스트의 사용법은 지금 배울 시기가 아니다..

https://opentutorials.org/module/1335/8636

리스트 (List) - Data Structure (자료구조)

 

---

✅  Linked List와 Array List

자바에는 1개의 리스트만 지원하는게 아니라 2개의 리스트를 제공해준다.

바로 Linked List와 Array List이다.

 

필요하다면 프로그래머가 직접 구현해서 써야하니까 두 리스트의 차이점을 공부해보자.

 

⚠️  Array List 

- 인덱스를 이용해서 데이터를 가져오는 것이 빈번할 때 사용하면 좋다. (Linked List보다 빠르다)

   ▶︎ 메모리 상의 주소를 정확하게 참조해서 가져오기 때문이라고 한다.

   ▶︎ 어디로 가야할지 집의 주소(동, 호수까지)를 정확히 알고 있는 것과 모르고 집을 찾는 것은 큰 차이가 있는 것처럼

   ▶︎ 따라서 인덱스만 알고 있다면 Array List에서 데이터를 가져오는 것이 더 빠르다. 

- Array List는 내부적으로 데이터를 [배열]에 저장하기 때문에

  배열의 특성상 리스트의 처음이나 중간에 저장하면 이후의 데이터들은 한칸씩 뒤로 물러나야한다.

- 중간에 빈자리가 생기면 순차적으로 하나씩 앞으로 당겨와야한다.

리스트에 데이터 추가 예시

 

 

⚠️  Linked List 

- 데이터의 추가/삭제가 빈번하다면 Linked List를 사용하는 것이 효과적이다.

- Linked List는 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한다. (*별첨1)

- Array List에서는 엘리먼트였지만 Linked List에서는 연결된 엘리먼트들을 노드(node) 혹은 버텍스(vertex)라고 부른다.

  ▶︎ 노드(node)는 최소 두가지 정보를 알고 있어야 한다. 노드의 값(데이터)과 다음 노드이다. (= Data field와 Link field)

  ▶︎ 별첨2 그림을 참고하자.

- Linked List는 처음에 Head라는 것이 있다.

  ▶︎ 이건 출입문 같은 존재이다.

  ▶︎ Linked List를 사용하는건 좋은데 시작점이 어디인지를 알아야 '시작으로부터 3번째의 데이터' 등을 찾을 수 있을 것이다. 그 시작점을 찾기 위해 존재하는 것이라고 보면 된다.

  ▶︎ first 라는 이름으로 사용하기도 한다. 어쨌든 중요한 점은 head는 첫번째 노드를 가리킨다는 것.

- 노드 추가/삭제 시 엘리먼트의 자리 이동은 필요하지 않고 참조값(link field)만 변경하면 된다.

- 만약 노드가 없다면 null list라고 하는데, 이때는 HEAD = null이 된다.

- 마지막 노드가의 link field에는 null이 들어간다.

---

🤜  별첨1

Linked List를 이해하기 위해서 컴퓨터 구조를 조금 공부해야한다.

컴퓨터는 CPU, 메모리, 스토리지가 중요한 부품이라고 할 수 있는데

메모리는 속도가 빠른 대신 용량이 적고 전기를 차단하면 데이터가 사라진다.

스토리지는 속도가 느린 대신 용량이 크고 전기를 꺼도 데이터가 남아있다.

 

데이터는 스토리지에 저장되어야 하지만, 스토리지는 CPU와 일하기에는 너무..너무 느리다.

그래서 프로그램을 실행할 땐 스토리지에서 메모리로 프로그램과 데이터가 옮겨지고 CPU는 메모리에 로드된 데이터로 산술연산 등 작업을 한다.

 

Array List는 메모리 상에서 모든 데이터가 순서대로 쭉 붙어있어야 했지만

Linked List는 메모리 상에서 꼭 한 위치에 모두 다닥다닥 순서대로 붙어있을 필요가 없다.

각 엘리먼트들이 '다음 사람(?)은 누구'(정확하게는 '어느 위치에 있다')라고 알려줄 수 있는 정보를 가지고 있기 때문이다.

그래서 연결(link)된 리스트라고 한다.

 

🤜  별첨2

※ head는 포인터가 될 수도 있고, 더미 노드(data는 들어있지 않고, 다음 노드를 가리키는 노드)가 될 수도 있다고 한다.

 

 

이 정도의 기초 지식만 배우면 나머지는 42 과제를 하면서 더 필요한 내용을 습득할 수 있을 것 같다.