[TIL]Data Structure 02)Linked list

🤔 linked list를 알기전에 알아야할것? 🙋

data structure에서 가장 중요한 부품이자 대상인 Memory!

> data structure의 미션은, '메모리의 효율적 사용'에 있기 때문!

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

• CPU : 생각하고 연산하는일을 함.

  데이터 연산속도 가장 빠름.

• Memory:

  가격 ↑, 용량 ↓, 전원꺼지면 데이터 사라짐.
  메모리 > storage(상대적으로 데이터를 가져오는 속도)

• Storage (HDD / SSD / 플로피디스크..) : 파일 등 데이터를 저장하는 곳.

  가격 ↓, 용량 ↑, 전원이 꺼져도 데이터가 저장되있다.

❗만약 storage에서 메모리를 거쳐 cpu가 아닌, 바로 cpu로 데이터를 가져온다면?
: storage의 데이터가져오는 속도가 너무 느리기 때문에, 반드시 메모리를 거쳐서 데이터를 가져와야함.

                  그림 01. array list 와 linked list의 데이터 구조 비교

array vs linked list의 구조 비교

• array : 같은 엘리먼트들이 메모리상에 연속적으로 붙어있다.
• linked list : 각각의 엘리먼트들이 여기저기 메모리상에 랜덤으로 흩어져있지만, 다 ⭐연결되어있다!

메모리를 건물의 사무실들에 비교해보자.

각 사무실에는 사무실의 호수가 있을텐데, 이걸 메모리로 치면 주소가 된다.
각 메모리의 주소가 가리키는 사무실, 즉 공간에는 데이터가 저장되어있다.

• array list의 장점: 공간의 수가 정해져있으므로, 특정 사무실을 찾아갈때에 속도가 빨라서,
  효율적으로 탐색이 가능하다.

• array list의 단점: 모든 사무실의 인원이 꽉 차게된다면, 공간을 더 늘릴 수 없으므로,
  새 건물로 이사하거나 해서 더 큰 공간으로 이동하는 수 밖에 없을것이다.
  메모리의 특징은, 각각의 주소에 접근하는데 걸리는 시간이 동일하다!

• linked list의 장점: 한 건물 내에서 한 회사가 임대한 사무실들이 서로 떨어져있어,
  직원이 늘거나 해도, 비어있는 사무실 아무데나 들어가면 되서 큰 걱정이 없다.

• linked list의 단점: 특정 사무실을 찾아가야 할 때, 첫번째 화살표가 가리키는 사무실을 먼저 찾아가야,
  그 다음다음의 사무실을 물어물어 찾아가서, 찾고자 하는 사무실을 찾게되므로, 효율성 ↓.

                  그림 02. linked list의 데이터 연결 구조

이러한 형태의 메모리를 random access memory(RAM)이라고 부른다.

이 메모리의 특성을 잘 알게된다면, 우리가 만들 애플리케이션은 아주 빨라지게 될 것이다.
이러한 메모리의 특성을 잘 살린 자료구조를 Linked list라고 부른다.

Linked list

: 크기가 동적인 자료구조. 여러개의 노드의 연결로 이루어진 자료구조.

• 새로운 데이터를 추가, 데이터의 위치를 탐색, 제거하는 기능이 있어야 함.

데이터 다루기에 관한 시간 복잡도

linked list : 어떠한 임의의 지점에 데이터의 추가, 삭제를 할 경우 : O(1)(상수시간)의 시간 복잡도를 갖음.

• 연결리스트의 각 노드는 인덱스를 갖지않는다.
  그래서 어떤 특정데이터를 연결리스트에서 검색하고자 할 경우,
  '처음부터 전체 연결리스트를 순차적으로 훓어야하며',
  이는 O(n)(선형시간)의 복잡도를 필요로 한다.

  자료구조       가져오기  추가하기  삭제하기
  linked list    O(n)      O(1)    O(1)

vs

array : 추가와 삭제에 대해 O(n)(선형시간)의 복잡도를 갖음.

node

: 자료구조를 구성하는 요소.

			      그림 03. 노드의 구성
                  

			      그림 04. 연결리스트의 구조

자바와 같은 객체지향 언어일 때,
객체에 '데이터 필드(DATA field)', '링크 필드(Link field)' 를 만든다.

• 데이터 필드(DATA field)
  : 보통 value라는 이름의 변수를 사용한다. 노드의 값을 저장한다.

• 링크 필드(Link field)
  : 보통 next라는 이름의 변수를 사용한다. 다음 노드의 포인터 혹은 참조값을 저장해서, '노드와 노드를 연결'시킨다.

• HEAD
  : list를 하나의 건물로 표현한다면, '출입문'에 해당하는 것이 Head이다. 즉,
  linked list를 사용하려면 이 head가 가리키는, 첫번째 노드를 찾아야한다! 👀

예

1>2>3>4>5 라는 연결리스트가 있다면, 1,2,3,4,5는 value이고, > 는 next, 즉 주소가 된다.
[1,2,3,4,5]라는 배열이 있으면, 1,2,3,4,5는 데이터이고, array[0], array[1]등은 데이터가 담긴 위치를 말해주고있다.
또한 배열은 array.push()를 이용해서 데이터를 추가할 수 있고,
array.splice()를 이용해서 데이터를 제거할수있다.

그러나 연결리스트를 구현하려면 저렇게 쉽게 배열을 이용하면 공부가 안될테니,
객체를 이용해서 구현하는것이 가장 베스트일 것이다.

즉, 우리는 연결리스트를 이용해서 배열을 구현한다고 생각하면 될 것이다.

인용 출처
1. Linked list 개념 1 - 소개 - Data Structure(생활 코딩 영상)
2. Linked list 에 대해(블로그)