Linked List

20강. Linked List 소개

 

Lineked List를 이해하는 핵심 KEY는 바로 '연결' 

 

그 전에 알아야 할 건 바로 '메모리'

컴퓨터에서 가장 중요한 3요소

1. CPU

- 생각하고 계산하고 연산하는 역할

- 3개 중 속도가 가장 빠름

- 스토리지에 있는 데이터를 직접 가져다 쓰면, '어떤 데이터 처리해줄까?'라고 물어볼 때마다 스토리지는 2-3일 후에 대답을 들을 수 있음 ㅎㅎ

-> 그래서 반드시 스토리지에 있는 데이터를 '메모리'에 가져온 다음에 CPU가 메모리를 읽으면서 처리  

 

2. 메모리 (★)

스토리지에 비하면

- 가격이 굉장히 비쌈

- 용량이 아주 적고 컴퓨터를 끄면 데이터가 사라짐 

- 훨씬 빠르게 데이터를 저장하고 데이터를 가지고 올 수 있음

 

3. 스토리지

- 하드디스크, SSD 같은 저장장치

- 가격이 저렴함

- 용량이 크고 데이터가 꺼져도 데이터 저장됨 

 

// 자료구조의 대상은 바로 메모리.

자료구조의 미션 : 메모리의 효율적 사용

 

메모리를 건물로 비유해서 알아보자.

어느 주소로 가든 '같은 시간'이 걸린다는 특징이 있음.

이걸 RAM이라고 함 

둘은 메모리를 사용하는데 큰 차이가 있음.

 

Array List 

- 엘리먼트들이 '연속적으로' 위치

 

Linked List

- 엘리먼트들이 각각 '흩어져'있음

---

21강. Linked List의 구조

 

하나하나가 element인데, 

'연결'되어 있는 특성이 있기 때문에 element라는 이름보다는 'node' 또는 'vertex'라고 더 즐겨 사용한다. (마디, 꼭지점을 의미)

 

하나의 노드 안에는 두 개의 filed가 있음 

1) data field : 저장되어 있는 값 

2) link field : 다음 노드가 무엇인지 저장되어 있음 

- 첫 번째 노드가 무엇인지 알아야, 두번째 노드도 알 수 있음 

- 첫 번째 노드가 무엇인지는 head에 저장함

 

httlp://visualgo.net 

---

22강. Linked List 데이터 추가 (처음에 추가) 

85를 추가하고 싶으면 가장 먼저 해야하는 일은 

1) 85라는 노드를 생성하는 것

- 오른쪽 아래 코드를 보면 

  vertex라는 객체를 새로 만듦(input을 매개변수로 줘서 85를 받을 수 있었더 것)

- 그리고 이걸 temp라고 부르기로 한거지

2) 85 다음인 85.next를 = head로 해주면 됨

- head는 누가 리스트의 시작인가 하는 것 

  원래는 15였음

3) 85.next = head를 지정해주었는데

   지금 head는 15지.

-> 근데 삽입되어서는 head가 85가 되었기에 head = temp로 해주기

---

23강. Linked List 데이터 추가 (중간에 추가) 

 

1) 

Vertex temp1 = head (15를 가리키는 걸 temp1으로 해주기)

2) while문 등장

-- k라는건 2-> 1-> 0...  이렇게 1씩 감소하는 것

k 앞에 등장하고 있다는게 포인트

만약에 k가 현재 2라면, while (--k!=0)은 '1'과 0을 비교하는 것

-> 조건문에 따라서 temp1 = 6이 됨

-> 그리고 또 조건문에 따라서 k=1이니, 0과 0을 비교하는거니까 조건문 끝남

3) 

temp 2= 23가 됨 (temp1.next가 23이니)

4) 새로운 노드 만들기

5) temp1 다음을 새로운 노드로 가르키게 하기

6) temp2가 다음걸 가르키게 하기

 

cf) ArrayList였다면 제일 끝에서부터 한 칸씩 이동시킨 후에! 데이터를 추가해주었을거기에 더 느렸을 것

---

24강. Linked List 데이터 추가 (특정한 위치의 element 삭제하기) 

 

90을 삭제해보자

6의 next도, 90의 next도 23을 가리키게 됨

 

cur 는 current를 의미

 

1) cur = head (현재 15지)

2) 

k는 현재 2 -> 1과 0을 비교하는 것

cur = 6이 됨

3) 

tobedeleted = 90 (바로 삭제하지 않고, 이걸 변수에 담아뒀다는게 포인트)

4) cur.next = 23을 하기 위해서 3)을 해준 것. (next next 해줘야하니)

- 6의 next도, 90의 next도 23을 가리키게 됨

5) 

delte tobedeleted하면 됨

 

 

linked List가 더 까다롭다고 여겨지는게 정설 (Array List보다)

대신 실행 순서는 빠름 (성능이 좋음) 

vs Array List였다면 90 삭제해주고 한 자리씩 앞으로 땡기느라 시간이 오래걸렸을 것

---

25강. Linked List vs Array List

 

4 값을 꺼내고 싶을 때 

 

Linked List	Array List
첫 번째 노드 값이 4인지 확인 -> .next 통해 그 다음이 4인지를 확인 ->  .next 통해 그 다음이 4인지를 확인...

 

네 번째 인덱스의 값을 꺼내고 싶을 때

Linked List	Array List
0, 1, 2, 3  첫 번째 노드로 우선 접근. 그 다음 .next 해서 노드 count +1 물어물어물어서 이동해야 함	주소의 상대적 위치를 계산 주소로 바로 직접 접근함. 굉-장히 빠르게 데이터를 가지고 올 수 있음

Linked List	Array List
달팽이... 한 칸씩 찾아 찾아 데이터 가지고 와야 함	index를 이용해서 조회할 때 굉장히 빠름
앞, 뒤 값만 바꿔주면 되서 훨씬 빠르다.	문자열 추가/삭제할 때는 우선! 공간을 만들어주기 위해 뒤나 앞으로 얘들 다 한 칸씩 이동 시켜서, 공간 만들고, 그 다음에 해야해서 굉장히 느림...
포인터? 혹은 참조값으로 각각의 노드가 연결되어 있어서 노드를 메모리가 허용하는 한에서 무한대로 키울 수 있음	배열을 내부적으로 사용해서 본질적으로 Array가 가지고 있는 어느 정도를 넘기면 에러가 난다.

 

 

 

 

출처 : 생활코딩 Data Structure 49강 (20~ 25강)