[Python] 자료구조 LinkedList 구현하기

▏목적

 

      ◦  자료구조 Linked List 이해하기

      ◦  Python으로 Linked List 구현하기

 

 

 

 

▏자료구조 Linked List 란?

 

Linked List (연결 리스트)란 크기 변경이 유연한 자료구조다. 때문에 데이터를 자유롭게 삽입 · 삭제할 수 있다는 장점이 있다.

 

집합의 단위를 List, 각 요소들의 단위를 Node 라고 부른다.

LinkedList는 한 줄로 연결된 형태로, 리스트의 첫 번째 노드를 Head (헤드), 마지막 노드를 Tail (테일) 이라고 한다.

 

각 노드는 

1. 데이터의 내용을 담는 부분

2. 다음 노드의 주소값을 지닌 포인터 변수

로 구성되어 있다.

 

 

LinkedList를 배열과 비교하여 장단점을 살펴보자.

 

장점 - 삽입, 삭제의 용이성

 

배열은 index 로 크기가 정해져 있어 하나의 데이터를 삽입, 삭제한다면 그다음 모든 데이터들이 재배치되어야 한다.

또한, 처음에 할당한 크기를 초과한다면 새롭게 메모리를 할당해야한다.

 

LinkedList는 삽입, 삭제시 해당 노드를 가리키는 포인터 변수만 변경해주면 되므로 배열보다 삽입, 삭제가 빠르다.

이 경우의 시간 복잡도는 O(1) 이다.

 

 

단점 - 최악의 탐색 시간

 

배열은 데이터를 찾을 때 index 가 있어 검색에 효율적이다. index가 주어진다면 탐색시간은 O(1) 에 가능하다.

 

반면 리스트는 정해진 위치를 전혀 알지 못하기에 검색시 모든 데이터를 순회하여 찾아야한다.

때문에 최악의 경우 시간 복잡도는 O(n) 다.

 

 

 

▏Linked List 종류

 

1. Singly Linked List (단순 연결 리스트)

 

Linked List의 가장 기본적인 형태다. 각 Node 당 한 개의 포인터를 가지며 그 포인터는 다음 노드의 위치를 가리킨다. 가장 마지막인 tail은 다음 노드가 없으므로 tail의 포인터 변수는 Null 이다.

 

2. Doubly Linked List (이중 연결 리스트)

 

단순 연결리스트의 단점을 보완한 것으로 앞 노드의 주소를 보관하기 위한 포인터(prev)를 가진다.

 

3. Circular Singly Linked List (원형 단순 연결 리스트)

 

단순 연결리스트의 tail이 Null 이 아닌 Head 를 가리켜 원형이 되도록 한다.

 

4. Circular  Doubly Linked List (원형 이중 연결 리스트)

 

이중 연결리스트에서 head의 prev 포인터를 tail로, tail의 next 포인터를 head 로 지정한 형태다.

이를 통해 최소한의 노드만을 거쳐 조금 더 효율적으로 삽입,삭제를 할 수 있다.

 

 

 

▏Python으로 LinkedList 구현하기

 

아래 설명하지 않은 메서드를 포함한 전체 코드를 보고싶다면 내 깃허브인 아래 링크를 클릭하면 된다.

https://github.com/yujin0131/Algorithm-DataStructure/blob/master/DataStructure/LinkedList.py

 

 

ㅇ prepend : 맨 앞 ( head )에 node 추가

def prepend(self,value):
	newNode = Node(value)
	if self.head is None:
		self.head = newNode
        self.tail = newNode
	else:
		newNode.next = self.head
        self.head = newNode
	self.length += 1
    return True

 

ㅇ append : 맨 뒤 ( tail )에 node 추가

def append(self, value):
    newNode = Node(value)
    if self.head is None:
        self.head = newNode
        self.tail = newNode
    else:
        self.tail.next = newNode
        self.tail = newNode
    self.length += 1
    return True

 

ㅇ insert : 특정 index에 node 추가

def insert(self, index, value):
	# if index < 0 or index >= self.length:
	#     return None
	if index == 0:
		return self.prepend(value)
	if index == self.length - 1:
		return self.append(value)

	newNode = Node(value) # 받아온 노드
	temp = self.get(index - 1) # 원래 해당 index 값 temp 노드에 옮김
	newNode.next = temp.next # 원래 index.next 를 newNode.next 에 옮김
    temp.next = newNode # temp.next 에 새로운 newNode

    self.length += 1
    return True

 

ㅇ popFirst : 맨 앞 ( head ) 값 삭제

def popFirst(self):
    if self.length == 0:
    return None
    temp = self.head
    self.head = self.head.next
    temp.next = None
    self.length -= 1
    return temp

 

ㅇ pop : 맨 마지막 ( tail ) 값 삭제

def pop(self):
    if self.length == 0:
        return None
    temp = self.head
    pre = self.head
	
    while temp.next:
        pre = temp
        temp = temp.next
    self.tail = pre
    self.tail.next = None
    self.length -= 1

    if self.length == 0:
        self.head = None
        self.tail = None
    return temp

 

ㅇ remove: 특정 index값 삭제

def remove(self, index):
    if index < 0 or index >= self.length:
        return None
    if index == 0:
        return self.popFirst
    if index == self.length - 1 :
        return self.pop
        
    prev = self.get(index - 1)
    temp = prev.next
    prev.next = temp.next
    temp.next = None
    self.length -= 1
    return temp

 

 

 

 

▏참고자료

 

https://fomaios.tistory.com/entry/DataStructure-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90Linked-List

 

https://recordofwonseok.tistory.com/m/111

 

https://lamarr.dev/datastructure/2020/04/02/01-linked-list.html