데이터 구조 - (4) 연결 리스트

리스트

출처 : 쉽게 배우는 자료구조 with 파이썬

위와 같이 배열 리스트로 구현하는 것과 아래와 같이 연결 리스트로 구분하는 형식이 있다.

보편적으로 배열 리스트를 자주 사용하는데, 아래와 같은 객체 구조를 가진다.

출처 : 쉽게 배우는 자료구조 with 파이썬

배열 리스트 즉 내장 리스트는 한계를 가진다.

아래 사진과 같이 3번 원소에 추가하기 위해 뒤의 원소를 모두 shift한다.

즉 추가 혹은 제거할 때 이러한 불필요한 shift를 거치는 등 비효율적이다.

그렇기에 이를 해결할 연결 리스트를 사용하는 것이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

 

연결 리스트

연결 리스트는 배열의 공간 낭비를 피할 수 있는 자료구조이다.

원소가 추가될 때마다 공간을 할당받아 추가하는 동적 할당 방식을 따른다.

​

노드는 원소를 저장하는 item 필드와 다음 노드를 가리키는 next 필드로 구성된다.

첫 노드는 head라고 부른다. numitems는 리스트에 들어 있는 원소의 총 수가 있다.

출처 : 쉽게 배우는 자료구조 with 파이썬

삽입을 위해서 아래와 같이 코드가 구현된다.

맨 앞에 노드를 삽입할 때와 그 외의 경우로 나눠진다.

if i==0: #맨 앞
   newNode.item=x
   newNode.next=__head
   __head=newNode
   __numItems+=1
else: # 그 외
   newNode.item=x
   newNode.next=prev.next
   prev.next=newNode
   __numItems+=1

이를 두 가지 경우로 나누지 않고 사용하는 방법이 있다.

이는 더미 헤드 노드를 활용하는 것이다

출처 : 쉽게 배우는 자료구조 with 파이썬

.

원래 __head는 None값을 가진다.

그렇기에 맨 앞에 값을 추가하는 경우 직전 노드가 존재하지 않았다.

하지만 더미 헤드를 사용하여 이 문제를 해결해 코드를 하나로 표현할 수 있다.

삭제할 때도 마찬가지이다.

newNode.item=x
newNode.next=prev.next
prev.next=newNode
__numItems+=1