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

💡 연결 리스트 (Linked List)

👉 데이터를 링크로 연결해서 관리하는 자료구조

👉 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않는다.

---

💡 연결 리스트의 장점

👉 데이터 공간을 미리 할당할 필요가 없다.

• 비어있는 자리에 데이터를 만들어주고 링크로 연결만 하면 되기 때문이다.

👉 즉, 리스트의 길이가 가변적이라 데이터를 추가하고 삭제하는데 용이하다.

• 구현 관점보다는 메모리 관리 측면에서 유리하다.

---

💡 연결 리스트의 단점

👉 연결구조를 위한 별도의 데이터 공간이 필요하다.

• 다음 데이터의 위치가 어딘지 찾아 링크로 연결해야하기 때문에 별도의 데이터 공간이 필요하다.

👉 연결 정보를 찾는 시간이 필요하다. (배열보다는 접근 속도가 상대적으로 느리다.)

• 다음 메모리가 링크된 위치가 멀리 떨어져 있는 경우 해당 메모리를 빨리 찾기 위한 공간에 따로 적재해줘야 한다.

👉 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업이 필요하다.

---

💡 연결 리스트 기본 구조

👉 노드 (Node)

• 데이터 저장 단위로, 값과 포인터로 구성되어 있다.
• 포인터 (Pointer) : 다음 노드나 이전 노드의 연결 정보 (링크 연결 작업하는 부분)

---

💡 연결 리스트 기본 연산

👉 데이터 추가

• 데이터 추가 위치 (head, 중간, tail) 에 따른 연결 작업 필요
• 가장 앞에 데이터를 추가하는 경우

1. 추가할 데이터를 담을 노드를 생성하고 데이터를 넣어준다.
2. 링크 연결 작업 (생성한 노드가 기존 head를 향하도록)
3. head 이전 작업 (기존 head -> 새로 생성한 노드)

• 가장 끝에 데이터를 추가하는 경우

1. 추가할 데이터를 담을 노드를 생성하고 데이터를 넣어준다.
2. head로부터 끝 노드까지 순회한다.
3. 링크 연결 작업 (마지막 노드 -> 새로 생성한 노드)

• 중간에 데이터를 추가하는 경우

1. 추가할 데이터를 담을 노드를 생성하고 데이터를 넣어준다.
2. head로부터 데이터 추가 위치 직전 노드까지 순회한다.
3. 링크 연결 작업 (추가 위치 직전 노드 -> 새로 생성한 노드 -> 기존 직전 노드가 가리키던 노드)

👉 데이터 삭제

• 데이터 삭제 위치 (head, 중간, tail) 에 따른 연결 작업 필요
• 가장 앞에 데이터를 삭제하는 경우

1. 삭제할 대장 노드를 별도의 변수로 지정해준다. (delete_node)
2. head 이전 작업 (삭제할 대상 노드 head -> 다음 노드)
3. delete_node 삭제 (JAVA의 경우 Garbage Collection 기능에 의해 더 이상 해당 메모리를 레퍼런스 하고 있는 대상이 없다면 자동으로 지워주기 때문에 코드 작성시 따로 delete_node를 하지는 않는다.

• 가장 끝에 데이터를 삭제하는 경우

1. head로부터 끝 노드까지 순회한다.
2. 가장 마지막 노드 삭제
3. 삭제한 노드 직전 노드의 링크 처리

• 중간에 데이터를 삭제하는 경우

1. head로부터 데이터 삭제 대상 노드까지 순회하고 해당 노드를 별도의 변수로 지정해준다.
2. 삭제 대상 이전, 이후 노드의 링크 연결 작업 (이전 노드 -> 다음 노드)
3. delete_node 삭제