자료구조: 연결 리스트(Linked List)

 

연결 리스트(Linked List)

: 데이터를 분산된 메모리 공간에 저장하고 이들을 서로 연결한 자료구조

• 연결 리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근할 수 있음
• 배열의 단점을 해결하기 위해 고안된 구조
  
  • 배열의 단점
    
    • 연속된 메모리 공간이 필요함
    • 초기에 크기를 정해야 하기 때문에, 메모리가 낭비될 수 있음
      ⇒ 저장하려는 데이터들을 메모리 공간에 분산해서 할당하고, 이들을 서로 연결해주면 됨
      ⇒ 노드(Node)를 만들어 연결하여 사용
      

 

 

 

노드(Node)

: 데이터와 다음 노드의 주소를 함께 저장하는 연결 리스트의 기본 단위

 

 

노드의 구조

• 데이터를 담는 변수 1개 + 다음 노드를 가리키는 변수 1개로 구성
• 데이터가 필요할 때마다 새로운 노드를 만들어서 데이터를 저장하고, 다음 노드를 가리키는 방식으로 연결함
  ⇒ 이런 구조이기 때문에 연결 리스트라고 부름

 

 

 

연결 리스트의 장단점

장점

• 배열처럼 초기에 크기를 정할 필요가 없음
  → 데이터를 추가할 때는 빈 메모리 아무 곳에 데이터를 생성하고 연결만 해주면 됨
• 중간에 데이터를 삽입할 때, 포인터(가리키는 다음 노드)만 바꿔주면 되므로 삽입이 간단함
  ↔  배열은 중간 삽입 시 모든 데이터가 밀려나므로 오버헤드 발생

 

단점

• 데이터들이 전부 떨어져 있어서 원하는 데이터에 바로 접근할 수 없음
  → 원하는 데이터를 찾으려면 처음부터 차례로 탐색해야 함
  
  • ex) 4번째 데이터를 찾으려면 ⇒ 1번 노드에서 다음 노드 찾기 → 2번 노드에서 다음 노드 찾기 → 3번 노드에서 다음 노드 찾기 → 4번 데이터 찾음
  ↔ 배열은 메모리의 연속된 공간에 할당되어 있어서 시작 주소만 알면 뒤에 있는 데이터에 접근하기 쉬움(O(1)의 성능)

 

 

 

배열과 연결 리스트 비교

	배열	연결 리스트
크기	고정	동적 (데이터가 필요할 때마다 노드를 만들어서 연결)
할당 주소	연속된 공간에 할당	불연속된 공간에 할당 (힙 영역에 런타임 중에 할당)
데이터 참조	빠름 (O(1))	느림 (O(n)) (앞에서부터 해당 노드까지 접근해야 함)
삽입/삭제	느림 (O(n)) (기존의 모든 데이터를 옮겨야 함)	느림 (O(n)) (삽입하려는 노드까지 노드를 계속 타고 들어가야 함)

 

 

 

---

추상 자료형(Abstract Data Type)

: 어떤 데이터와 그 데이터를 연산하는 기능을 표기하는 것을 말함

• ex) 세탁기라는 기계에 옷(데이터)을 넣고 빨래(연산 기능)를 함
  → 사용자는 세탁기의 내부 동작을 몰라도 빨래 기능을 사용할 수 있음
  → 즉, 데이터 구조의 세부 구현을 숨기고 기능(연산)만을 외부에 제공하는 방식

 

 

 

연결 리스트의 추상 자료형

• 연결 리스트는 노드(Node)라는 단위로 데이터를 저장하고, 각 노드는 다음 노드를 가리킴
• 여기서는 데이터를 정수형으로 가정함

printAll()	연결 리스트의 모든 데이터 출력 → 리스트의 처음부터 끝까지 순차적으로 탐색하면서 모든 데이터를 출력함
clear()	연결 리스트의 모든 데이터 제거 → 연결 리스트를 비워 초기 상태로 만들고, 모든 노드를 순회하며 삭제함
insertAt(index, data)	원하는 인덱스의 데이터 삽입 → 지정한 위치에 새 데이터를 삽입, 삽입 지점 전까지 노드를 탐색해야 함
insertLast(data)	마지막 데이터 뒤의 데이터 삽입 → 리스트의 마지막에 새로운 데이터를 추가, insertAt으로도 가능하지만 비효율적일 수 있음
deleteAt(index)	원하는 인덱스의 데이터 삭제 → 지정한 위치의 노드를 삭제, 인덱스까지 순차적으로 탐색 필요
deleteLast()	마지막 데이터 제거 → 리스트의 끝에 있는 노드를 삭제, 마지막 직전 노드까지 탐색해야 함
getNodeAt(index)	원하는 인덱스의 데이터를 읽는 기능 → 해당 인덱스 위치의 데이터를 반환, 순차 접근 필요