선형자료구조 - 연결 리스트

📌 연결 리스트

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

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

 

Linked List 구조

 

장점

• 데이터 공간을 미리 할당할 필요 없이 빈 공간에 할당해도 됨
  
  
• 리스트의 길이가 가변적이기 때문에 데이터 추가 / 삭제 용이 (메모리 관리 측면)

 

단점

• 연결 구조를 위한 별도 데이터 공간이 필요
  • 배열은 인덱스를 통해 바로 데이터에 접근이 가능했으나 연결리스트는 다음 연결해야하는 데이터를 링크로 연결해서 그 링크에 대한 공간이 필요
    
    
• 연결 정보를 찾는 시간이 필요 (메모리 상 연속된 위치가 아니라면, 접근 속도가 상대적으로 느림)
  
  
• 데이터 추가 및 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요

 

노드

• 데이터 저장 단위, 값과 포인트로 구성
  
  
• 포인터 : 다음 노드나 이전 노드의 연결 정보
  
  
• 노드에는 값을 저장하는 공간과 그 다음 노드의 위치를 가리키는 링크 부분이 있음
  
  
• 단방향 연결 리스트 구조 시 맨 앞 첫번째 노드를 head, 마지막 노드를 tail
  
  
• 각 노드안에서의 data와 포인터는 여러 개일 수 있음

---

연결 리스트 기본 연산

데이터 추가

• 데이터 추가 위치(head, 중간, tail)에 따른 연결 작업 필요

Linked List 데이터 추가

 

1. 가장 앞에 추가
   • 추가할 데이터를 담을 노드 생성(head 이전)
     
     
   • 기존 head와 링크 연결 작업
     
     
   • head 이전 작업
     
     
     
2. 가장 끝에 추가
   • 보통 단방향 연결리스트는 head만 있음
     
     
   • 추가할 데이터를 담을 노드 생성
     
     
   • head로부터 시작해 포인터가 가리키는 것이 없을 때까지 순회
     
     
   • 링크 연결 작업
     
     
     
3. 중간에 추가
   • 중간에 새로운 노드를 생성
     
     
   • 추가할 노드 이전까지 head로부터 시작해 데이터 추가 위치 직전 노드까지 순회
     
     
   • 추가한 노드의 포인터를 다음 노드와 링크 연결 작업
     
     
   • 링크 연결 시 주의할 점은 추가한 노드의 정보가 유실되지 않도록 해야함
     • 추가하기 전에 이전 포인터가 가리키는 정보가 다음 연결할 노드의 정보를 갖고 있어야 함.
     • 데이터를 추가한 노드의 데이터를 가리키면 데이터가 유실되기 때문에 새롭게 생성된 노드의 데이터를 이전 포인터가 원래 가리키는 데이터로 할당한 뒤 추가 생성된 데이터를 가리켜야함

데이터 삭제

• 가장 앞과 끝에 삭제해야되는 부분은 데이터 추가와 작업 동일

 

Linked List 데이터 삭제

 

 

1. 중간에 삭제
   
   • 삭제하기 이전 노드까지 순회하고, 삭제할 노드 지정
     
     
   • 삭제 대상 이전 - 이후 연결 정보 => 삭제 대상 이전 - 상제 대상 연결 정보 로 연결 작업
     
     
   • 대상 노드 삭제
     
     

 

(이미지 출처 : https://velog.io/@woojinn8/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-List )