학습한 내용
연결 리스트(Linked List)
블로그 참고하여 내용정리
- 단열 연결 리스트(singly-linked list)
- 다음 원소를 가르키는 next 포인터 또는 레퍼런스(연결 링크)
- 마지막 원소에는 빈 링크 null
- 연결 링크가 next 포인터로만 구성이 되어있어서 리스트를 한 방향으로만 다룰 수 있다.
- 반드시 첫번째 원소(head)가 필요하다.
- 이중 연결 리스트(doubly-linked list)
- 각 노드별로 다음원소에 대한 링크와 앞 원소에 대한 링크도 있다.
- 어떤 원소로 시작하던 리스트를 앞, 뒤 양 방향으로 다룰 수 있다.
- 원형 연결 리스트(circularly-linked list)
- head나 tail 이 없다.
- 시작점을 제대로 파악하지 않으면 무한루프에 빠질 수 있다.
Linked list
Linked list - Data Structure (자료구조)
생활코딩 Linked list, Hello coding 알고리즘 책보고 정리함
- 자료구조의 미션은 메모리의 효율적 사용
- Linked list에서는 요소를 node, vertex라고 부른다.
- Linked list 를 사용하면 원소를 메모리의 어느곳에나 둘 수 있다.
- 흩어져있는 임의의 메모리 주소들이 하나의 목록으로 연결되어 있는 것
- Linked list의 장점
- 요소들의 중간에 삽입할 때 용이
- 삭제할 때 용이
- Linked list의 문제점
- 마지막 원소를 보고 싶을 때 바로 읽을 수 없다.
- 주소를 타고 타고 접근해야한다. → 순차접근
- 원소에 접근할 때는 배열의 인덱스 접근이 더 용이하다. → 임의접근
Lined list의 구조
- 노드들의 모임
- 노드는 노드의 값과 다음 노드에 대한 정보(포인터)를 갖고있다.
- head
- 건물의 출입문 같은 것
- Linked list를 사용하려면 head가 가르키는 첫번째 노드를 찾아야함
빅오 표기법
[자료구조 알고리즘] 빅오(Big-O)표기법 완전정복
출처 : 유튜브 엔지니어대한민국, 이 영상 너무 좋다.
- 알고리즘의 속도는 시간이 아니라 연산횟수가 어떻게 증가하는지로 측정
- 원소의 개수가 커질수록 이진탐색의 속도가 단순탐색의 속도보다 훨씬 빨라진다.
- 이진 탐색은 크기가 n인 리스트를 확인하기 위해서 log n번의 연산이 필요하다. → O(log n)
빅오 표기법의 예
- O(log n), 로그시간 : 이진탐색
- O(n), 선형시간 : 단순탐색
- O(n*log n) : 퀵정렬과 같은 빠른 정렬 알고리즘
- O(n2) : 선택정렬과 같이 느린 정렬 알고리즘
오늘 한 일
- 생활코딩 영상과 Hello coding 그림으로 개념을 이해하는 알고리즘 책 보고Linked list, 이진탐색, 빅오표기법 학습
- 미션 해결 완료
Todo
(내일)
Doubly linked list (이중 연결 리스트) - Data Structure (자료구조)
알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기
- 알고리즘 책 보고 복잡도 학습하기
- 학습정리에 나온 내용 학습하고 정리하기
벌써 미션 완료 하셨군요 "미션진행한 것 README.md 작성하기"는 나중에서 어디에서 볼 수 있나yeon?