목록 형태로 이루어진 데이터 형식.
목록을 이루는 개별 요소를 노드 (Node)라고 하고 첫 번째 노드를 헤드 (Head), 마지막 노드를 테일(Tail)이라고 함.
리스트의 길이는 헤드부터 테일까지의 노드 개수와 같다.
배열과의 차이: 배열은 크기를 지정해줘야 하고 생성 후에 크기를 변경할 수 없다.
리스트는 데이터 집합 보관 기능을 가지면서도 유연하게 크기를 바꿀 수 있는 자료구조이다.
링크드 리스트는 노드를 연결해서 만든 리스트, 링크드 리스트의 노드는 데이터를 보관하는 필드와 다음 노드와 연결 고리 역할을 하는 포인터로 이루어짐.
노드 생성/소멸 : malloc()으로 할당, free()로 해제
노드 추가 연산: 링크드리스트의 테일 노드 뒤에 새로운 노드를 만들어 연결하는 연산. 꼬리 붙이기
노드 탐색 연산: 헤드부터 시작해서 차근차근 노드의 개수만큼 거쳐가야 원하는 요소에 접근할 수 있음. 찾고자 하는 요소가 N번째에 있으면 N-1개의 노드를 거쳐야 함.
노드 삭제 연산: 링크드 리스트 내 노드를 제거하는 연산으로 삭제하고자 하는 노드를 찾은 뒤 해당 노드의 이전 노드가 삭제할 노드가 가리키던 노드를 가리키게 함.
노드 삽입 연산 : 노드와 노드 사이 새로운 노드를 끼워 넣는 연산
노드 개수 세기 연산: 링크드 리스트 내 존재하는 노드의 개수를 세어 그 결과를 반환.
장점 - 새로운 노드의 추가, 삽입, 삭제가 쉽고 빠르다
단점 - 다음 노드를 가리키려는 포인터 때문에 각 노드마다 추가적인 메모리가 필요, 특정 위치에 있는 노드에 접근하기 위한 비용이 크고 시간이 많이 소요됨. n번째 위치에 있는 노드에 접근하려면 n회의 노드 탐색 루프를 실행해야 접근할 수 있음.
더블 링크드 리스트: 링크드 리스트의 탐색 기능을 개선한 자료구조. 양방향 탐색이 가능.다음 노드와 이전 노드를 가리키는 포인터를 갖고 있음.
노드 생성/소멸: 링크드 리스트에서 이전 노드 (PrevNode)를 초기화시키는 부분만 추가되고 나머지 동일.
노드 추가 연산: 새로 추가된 노드의 이전 노드(PrevNode)가 기존 테일이었던 코드를 가리키게 하는 것만 추가되고 나머지 동일.
노드 삭제 연산: 삭제할 노드의 이전 노드는 삭제할 노드의 다음노드를 가리키고 다음 노드는 이전 노드를 가리키게 바꿈. 삭제할 노드의 NextNode와 PrevNode는 NULL로 초기화.
노드 삽입 연산: 삽입할 노드의 PrevNode 포인터로는 이전 노드를 , NextNode 포인터로는 다음 노드를 가리키게 하고 이전 노드의 NextNode 포인터와 다음 노드의 PrevNode 포인터를 새 노드를 가리키게 함.
노드 개수 세기 연산: 링크드 리스트와 동일.
환형 링크드 리스트: 머리가 꼬리를 물고 있는 형태의 링크드 리스트로 더블 링크드 리스트로도 링크드 리스트로도 만들 수 있음.
테일의 다음 노드 포인터가 헤드를 가리키도록 하면 됨. 테일은 헤드의 이전 노드, 헤드는 테일의 다음 노드이다.
여기선 더블 링크드 리스트로 구현했음.
노드 추가 연산: 리스트가 비어 있을 때 새 노드를 추가 시 이전 노드도 자신, 다음 노드도 자신을 가리킨다.
리스트가 비어 있지 않은 경우 추가 연산 과정을 테일과 헤드 사이 새 노드를 삽입한다고 이해하기.
노드 삭제 연산: 테일과 헤드가 연결되어 있다는 사실에 주의, 크게 다르지 않음.
'자료구조' 카테고리의 다른 글
| 정렬 알고리즘 {버블 정렬, 삽입 정렬, 퀵 정렬} (0) | 2025.04.17 |
|---|---|
| 트리 {이진트리, 수식트리, 분리 집합} (0) | 2025.04.17 |
| 큐 {순환 큐, 링크드 큐} (0) | 2025.04.16 |
| 스택 {배열 기반 스택, 링크드 리스트 기반 스택} (0) | 2025.04.15 |
| 자료구조란 (0) | 2025.04.15 |
