📌 Linked List
연결리스트 : 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조
노드 : 데이터 필드 + 다음 노드에 대한 참조
원소의 수가 가변적이다
삽입 / 삭제 용이 → O(1)
랜덤 액세스 불가능하다. 순차접근 → O(n)
포인터를 위한 여분의 메모리 공간이 필요하다
📌 단순 연결 리스트
sequential 순차표현 VS linked 연결된 표현
순차표현
- 연속된 원소들이 일정한 거리만큼 떨어져서 저장
- 탐색 빠름. 랜덤 액세스 → O(1)
- 스택이나 큐의 원소 삽입/삭제에 적합
- 순서리스트에서 임의 원소의 삽입/삭제 비용이 크다 → O(n)
연결된 표현
- 각 원소들이 기억 장소 내의 어떤 곳에나 위치
- 노드 = 데이터 + 링크(포인터)
first = 8일때
data[8] = BAT : 시작 데이터 → 3번 인덱스
link[3] = 4 : 다음 주소
data[link[3]] = data[4] = EAT : 데이터
BAT → CAT → EAT → FAT → HAT … → WAT
연결리스트를 그리는 일반적인 방법
노드 삽입
삽입 시 리스트에 있는 다른 원소들의 이동 불필요
link 필드를 위한 저장 공간이 추가로 사용
ex) FAT다음에 GAT 삽입
- 현재 사용하고 있지 않은 노드 a 할당
- 노드 a의 data 필드에 GAT 설정
- a의 link 필드가 FAT다음노드, 즉 HAT를 가리키도록 (이게 꼭 먼저여야함!)
- FAT를 포함한 노드의 link 필드가 a를 가리키도록
노드 삭제
ex) 리스트에서 GAT 삭제
- GAT 바로 앞에 있는 원소 FAT 찾기
- FAT의 link를 HAT의 위치로 설정
📌 원형 리스트
체인에서 마지막 노드의 Link 필드가 첫번째 노드를 가리킴
head 포인터는 항상 마지막 노드를 가리키도록 함 → O(1)시간에 삽입 가능
- 원형 리스트 처음에 삽입 새로운 node의 링크가 첫번째 노드를 가리키게 하고, 마지막 노드의 링크가 새로운 node 가리키게한다
- 원형 리스트 끝에 삽입 새로운 node의 link가 첫번째 노드를 가리키게 한다 head 포인터가 새로 삽입된 node를 가리키게 한다
헤더노드 : dummy 노드
공백 리스트를 특별한 경우로 처리할 필요 없음
📌 연결 스택과 큐
linked list를 기반으로 구현한 stack과 queue
연결 스택
top에서 노드 삽입/삭제 용이
top : 스택 톱 노드를 가리키는 전용 데이터 멤버
초기엔 top을 0으로 설정
연결 큐
뒤(rear)에서 삽입 용이
앞(front)에서 삽입 삭제 용이
초기엔 front, rear를 0(null)로 설정
📌 다항식
연결 리스트를 사용해서 다항식 구현
다항식의 덧셈
두 다항식 a,b
만일 두 항의 지수가 같으면 계수를 더하고, 합이 0이 아니면 결과에 대한 새로운 항을 만든다
b의 현재 항의 지수보다 a의 현재 항의 지수가 작으면 b의 항과 똑같은 항을 만들어 polynomial 객체에 첨가, b는 다음 항으로 이동
반대의 경우는 a에 대해 수행
📌 희소 행렬
0이 아닌 각 항은 행 원형 리스트와 열 원형 리스트에 위치
모든 원형 리스트는 헤더 노드를 포함
헤더노드
- down : 열 리스트 연결에 사용
- right : 행 리스트 연결에 사용
- next : 헤드 노드 들을 서로 연결
원소 노드
- down : 같은 열에 있는 0이 아닌 다음 항 연결
- right : 같은 행에 있는 0이 아닌 다음 항 연결
📌 이중 연결 리스트
양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
노드 구조
- 두개의 링크 + 한개의 데이터 필드
- left 필드 : 왼쪽 노드와 연결하는 포인터
- right 필드 : 오른쪽 노드와 연결하는 포인터
dummy node가 있으면 비어있을때 예외 발생안함
