오늘은 연결리스트의 기초에 대한 강의를 수강했다.
연결리스트 란?
각 요소를 포인터로 연결하여 관리하는 선형 자료구조이다.
데이터가 들어가게 되는 각 요소를 노드라고 부르며 알파벳이 있는 부분이 값을 담는 부분이고 동그라미가 있는부분은 다음 노드로 이어주는 포인터이다.
연결리스트의 특징은 아래와 같은데, 배열과는 정반대의 특징을 가졌다고 볼 수 있다. Singly Linked List, Doubly Linked List, Circular Linked List는 각각 단일 연결리스트, 이중 연결리스트, 환형 연결리스트 라고 부른다.
연결리스트에서 요소를 삭제하거나 추가할 때에는 아주 간단한 방법으로 진행된다.
삭제의 경우에는 삭제하고싶은 요소의 이전요소의 포인터 값을 삭제하고싶은 요소로 바꾸고 요소를 삭제한다.
이렇게 간단한 로직이기 때문에 상수시간이 소요된다.
요소의 추가의 경우에는 삭제보다는 복잡하지만 여전히 간단하므로 상수시간만이 소요되는데,
먼저 추가하고싶은 요소의 포인터를 추가하고싶은 자리의 다음요소에게 바꾸고, 추가할 요소의 이전요소의 포인터를
추가할 요소에게로 바꾸면 완료된다.
단일 연결리스트
연결리스트의 첫번째 노드를 Head 라고 부르며, 마지막 요소를 Tail이라고 칭한다. 마지막 Tail의 포인터 영역은 마지막 요소이기 때문에
Null 값이 들어가게된다.
요소추가의 로직은 위에서 설명한 방식과 동일하기 때문에 이미지로 대체하고 따로 언급하지 않겠다.
이중 연결리스트
단일 연결리스트와 같지만 자료의 순환이 양방향으로 이루어지기 때문에 단일 연결리스트보다 자료구조의 크기가 더 크다.
기본적인 요소 추가/ 삭제 로직은 단일 연결리스트와 같지만, 포인터로 이전요소를 다시 가리켜야 하며, Null값이 1번 값과 8번값에 두 군데 존재한다.
환형 연결리스트
단일이나, 이중 연결리스트에서 Tail이 Head로 연결되므로써, 메모리를 아낄 수 있는 연결리스트 구조이다. 계속해서 순환을 하기 때문에 포인터 값에 null이 들어가는 부분이 없다.
'알고리즘 > 알고리즘' 카테고리의 다른 글
| 알고리즘 강의 6일차 - 큐(Queue)의 기초와 알고리즘 (0) | 2023.03.09 |
|---|---|
| 알고리즘 강의 5일차 - 스택 알고리즘 (0) | 2023.03.08 |
| 알고리즘 강의 3일차 - 배열기초 (0) | 2023.03.06 |
| 알고리즘 강의 2일차 - 자료구조 기초 (0) | 2023.03.06 |
| 알고리즘 강의1일차 - 알고리즘 강의 수강을 시작하며 (0) | 2023.03.02 |