리스트 ADT / SLL / DLL / CDLL

리스트 ADT

• 목록 형태로 이루어진 자료구조
• 개별 요소 = 노드
• 첫번째 노드 → Head, 마지막 노드 → Tail

리스트와 배열의 차이

• 배열 - 생성 시 반드시 크기를 지정해야한다.
• 리스트 - 생성 시 크기를 지정하지 않아도 되며 길이 추가 및 축소가 자유롭다

---

SLL(Singly Linked List)

• 한 방향으로만 연결된 링크드 리스트
• 구조체를 선언하여 이용하며 한 구조체를 한 노드라고 칭함
• Linked List에 필요한 연산
  • 노드 생성
  • 노드 추가
  • 노드 탐색
  • 노드 삭제
  • 노드 삽입
• 더블 포인터를 사용하는 이유
  • 함수 안에서 head의 주소를 다른 주소로 할당할 경우 단순히 포인터가 가지고 있는 주소값만 전달 시 그 값을 복사해서 바꾸기 때문에 포인터가 가지고 있는 원본 주소값은 바뀌지 않는다.
  • 더블 포인터로 포인터 변수의 주소를 복사하여 전달하여야 해당 포인터가 가지고 있는 주소의 원본을 변경할 수 있는 것이다.

LinkdedList.c

0.00MB

LinkedList.h

0.00MB

Test_LinkedList.c

0.00MB

---

DLL(Doubly Linked List)

• 양방향으로 연결된 링크드 리스트
• 구조체에 앞, 뒤 노드의 주소를 담을 수 있는 포인터가 포하되어 있다.
• 따라서 앞 뒤로의 이동이 가능하다

 

DoublyLinkdedList.h

0.00MB

DoublyLinkedList.c

0.00MB

Test_DoublyLinkedList.c

0.00MB

---

CDLL(Circular Doubly Linked List)

• DLL이 동그랗게 연결된 구조

1. 노드가 하나일때
   • head이자 tail
2. 노드가 두개 이상일 때
   • tail의 다음 노드가 head를 가리킴

• 나머지는 DLL과 동

CircularDoublyLinkedList.c

0.00MB

CircularDoublyLinkedList.h

0.00MB

Test_CircularDoublyLinkedList.c

0.00MB

---

위 코드들은 헤더, main, 함수 파일이다.

각각 링크드리스트에서 구현해야하는 생성, 추가, 삭제, 탐색 코드들을 정리하였다.