[자료구조/선형구조] 연결 리스트

연결 리스트

• 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조

연결 리스트의 성질

1. k번째 원소를 확인/변경하기 위해 O(k)가 필요함
   • 우리는 첫 번째 원소의 주소만 알고 있기 때문, 차근차근 다음 주소로 넘어가며 찾아야 함
2. 임의의 위치에 원소를 추가/제거는 O(1)
   • 이전 원소에 다음 주소를 변경만 해주면 되기 때문에
   • 단, 추가/제거 하고 싶은 위치의 주소를 알고 있을 경우에만 O(1)
3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

연결 리스트의 종류

• 단일 연결 리스트 : 각 원소가 자신의 다음 원소의 주소를 들고 있음
• 이중 연결 리스트 : 각 원소가 자신의 이전 & 다음 주소를 둘 다 들고 있음
• 원형 연결 리스트 : 끝이 처음과 연결되어 있음
  • 각 원소가 이전과 다음 원소의 주소를 모두 들고 있어도 상관 X

배열 VS 연결 리스트

• BOTH → 선형 자료구조

	배열	연결 리스트
k번째 원소의 접근	O(1)	O(k)
임의 위치에 원소 추가/제거	O(N)	O(1)
메모리 상의 배치	연속	불연속
추가적으로 필요한 공간 (Overhead)	-	O(N)

---

기능과 구현

insert 함수

1. 새로운 원소를 생성
2. 새 원소의 pre 값에 삽입할 위치의 주소를 대입
3. 새 원소의 nxt 값에 삽입할 위치의 nxt값을 대입
4. 삽입할 위치의 nxt값과 삽입할 위치의 다음 원소의 pre값을 새 원소로 변경
5. unused 1증가

void insert(int addr, int num) { //삽입할 위치 addr, 삽입할 숫자 num
	dat[unused]=num;
    pre[unused]=addr; //삽입할 위치가 이전 요소이기 때문에.
    nxt[unused]=nxt[addr];
    if(nxt[addr]!= -1) pre[nxt[addr]]= unused; //삽입할 위치의 다음 원소의 pre값
    nxt[addr]=unused; //삽입할 위치의 다음값이 내가 새로 생성한 원소의 위치
    unused++;
}

맨 마지막 원소의 뒤에 새 원소를 추가할 경우, 삽입할 위치의 다음 원소는 존재하지 않기 때문에 if문 사용!

erase 함수

1. 이전 위치의 nxt를 삭제할 위치의 nxt로 변경
2. 다음 위치의 pre를 삭제할 위치의 pre로 변경

void erase(int addr){
	nxt[pre[addr]]=nxt[addr];
    if(nxt[addr]!=-1) pre[nxt[addr]]=pre[addr];
}

dummy node의 존재로 인해 그 어떤 원소를 지우더라도 pre[addr]는 -1이 아님이 보장되지만, 

마지막 원소를 지우면 다음꺼가 없을 수 있기 때문에 if문 붙여주기!