[Week2 자료구조/알고리즘] TIL 2일차 - 연결리스트

0) 추상적 자료구조(ADT)

자료구조의 내부구현은 제공하지 않고, 데이터의 형태를 선언하고 기능(연산)을 정의하는 것

 

1) 연결리스트란?

노드와 노드가 연결된 형태이다.

노드는 값을 담는 부분과 주소를 담는 부분으로 구성되어 있다.

일반 리스트에 비해 값을 접근하는 데는 오래 걸리지만(시간복잡도 :  O(1) vs O(n)), 데이터를 자유롭게 삽입 삭제 할 수 있다는 장점이 있다.

 

오늘 살펴볼 연결리스트는 기본 연결리스트, head가 더미노드를 가리키는 연결리스트, 양방향 연결리스트이다.

 

🥄기본 연결리스트

기본 연결리스트 형태

연결리스트는 노드가 연결된 형태이며,  head, tail, nodeCount로 구성된다.

• Head : 제일 앞 노드를 가리키는 포인터
• Tail : 제일 뒷 노드를 가리키는 포인터
• nodeCount : 연결리스트에 있는 노드의 개수

 

연산

연결리스트는 다음과 같은 연산이 제공된다.

• 특정 원소 참조 - getAt(pos) : pos번째 노드를 반환한다.
• 리스트 순회 - traverse() : LinkedList의 모든 노드 값을 반환한다.  
• 길이 얻어내기 - getLength() : LinkedList의 노드 개수를 반환한다.
• 원소 삽입 - insertAt(pos, newNode) : pos번째에 newNode를 삽입한다.
• 원소 삭제 - popAt(pos) : pos번째 노드를 삭제하고 값을 반환한다.
• 두 리스트 합치기 - concat(L) : LinkedList뒤에 L을 합쳐 반환한다.

 

클래스 다이어그램

데이터의 형태와 기능을 합친 클래스 다이어그램은 다음과 같다.

연산을 보면 맨 앞과 연관된 노드의 경우 연산을 따로 처리해야 한다.

head가 더미 노드(빈 노드)를 가리키게 하여 연산을 간단하게 해 보자.

 

☁️더미 연결리스트

기본 더미 연결리스트 형태

head 포인터가 dummy node를 가리키도록 하는 형태이다.

 

연산

해당 연결리스트의 연산의 종류는 기본연결리스트와 같다.

• 특정 원소 참조 - getAt(pos) : pos번째 노드를 반환한다.
• 리스트 순회 - traverse() : LinkedList의 모든 노드 값을 반환한다.  
• 길이 얻어내기 - getLength() : LinkedList의 노드 개수를 반환한다.
• 원소 삽입 - insertAt(pos, newNode) : pos번째에 newNode를 삽입한다.
• 원소 삭제 - popAt(pos) : pos번째 노드를 삭제하고 값을 반환한다.
• 두 리스트 합치기 - conccat(L) : LinkedList뒤에 L을 합쳐 반환한다.

+ 삽입, 삭제 연산의 장점을 극대화하기 위해 아래 두 가지 함수를 추가하여 연산을 간단히 해 보자.

• insertAfter(prev, newNode)
• popAfter(prev)

 

일반 배열은 인덱스를 이용해 값을 찾기 때문에 원소를 참조할 때의시간복잡도가 O(1)이다.

반면, 연결리스트는 앞에서부터 순서대로 값을 찾아 나가야 하기 때문에 시간복잡도가 O(n)이다.

기본 연결리스트나, 더미노드를 포함한 연결리스트 모두 다음 노트로 연결되어 있지만, 이전 노드로는 돌아가지 못하는 단점이 있다. 이 때문에 일반 리스트에 비해 시간 복잡도가 큰데, 이를 해결하기 위해 양방향 연결리스트에 대해 생각해 보자.

P : 다음노드로 이동할 수 있지만 이전 노드로 돌아가지 못함

S : 양방향 연결리스트

 

🍴양방향 연결리스트

양뱡향 연결리스트 형태

 

node에 prev포인터를 추가한다.

LinkedList에 head, tail 포인터가 더미 노드를 가리키게 한다.

이렇게 링크드리스트를 구현하면 데이터를 담고 있는 노드들은 모두 같은 모양이므로 연산이 간단해진다.

하지만, 메모리를 더 차지하는 단점이 있다.

 

 

클래스 다이어그램

데이터의 형태와 기능을 합친 클래스 다이어그램은 다음과 같다.

연산의 종류는 더미 링크드리스트와 유사하므로 생략한다.

 

head, tail 모두 더미 노드를 가리키므로 연산 시 별도의 처리를 덜 요한다.

결론) 양방향 연결 리스트는, 공간복잡도가 조금 증가하는 단점이 있지만, 구현이 편리하므로 자주 사용된다.

 

연결리스트의 모든 함수 구현은 깃허브 링크를 참고하자.

 

관련 라이브러리

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList