#3. 연결리스트 (Linked list) / python으로 구현

2023.10.01 - #2. 배열 (Array) / python list

#2. 배열 (Array) / python list

array는 이전글 참고해주세요.

이전글에서 List의 종류에는 array list와 linked list가 있다고 분류했습니다.

이 글에서는 Linked List를 알아보고 코드로 구현해보도록 하겠습니다. 

 

연결리스트의 구조

메모리상에 연속적으로 데이터를 저장하는 배열과 달리 연결리스트는 메모리상에 연속적이지 않게 데이터를 저장할 수 있는 자료구조입니다. 노드라는 단위로 구성되었고, 노드는 데이터와 다음 노드를 가리키는 주소로 만들어집니다. 

 

그리고 연결리스트의 가장 첫 노드를 가리키는 head가 존재합니다. 

 

* 연결리스트 이미지 참고 

 

출처: geeksforgeeks

연결리스트는 배열과 달리 메모리 상에서 연속적으로 존재하지 않아도 되기 때문에 메모리 사용이 자유로운 장점이 있지만, 주소값도 항상 같이 저장해야해서 메모리가 더 많이 쓰이게 됩니다.  이러한 자료구조의 차이로 인해 데이터를 삽입, 삭제, 검색 하는데 걸리는 시간복잡도가 달라집니다.

 

배열과의 시간복잡도 차이 

배열은 메모리상에 연속적으로 있기 때문에 특정 index의 값을 조회하는데 O(1)의 시간이 걸리는데 비해 연결리스트는 처음부터 연결된 노드를 하나하나 따라가면서 조회하기 때문에 O(n)의 시간이 걸리게 됩니다. 

 

대신 특정 위치에 값을 추가하고 싶을 때 배열은 한칸씩 값을 옮겨주어야 해서 O(n)의 시간복잡도를 가지는데 비해 연결리스트는 특정 위치의 연결만 수정해주면 되기 때문에 O(1)의 시간 복잡도를 가집니다. 

 

파이썬으로 연결리스트 구현하기 

1) 노드 class

노드는 값과, 다음 노드를 가리키는 주소로 구성됨

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

 

2) 연결리스트 class

• append(self,value): 맨 끝에 값 추가
  • Node 클래스에 값을 넘겨주어 새로운 node객체를 생성
    • 첫번째 노드일 경우 head가 node를 가리키도록 설정
    • 두번째 이상 노드일 경우 head는 변경하지 않고, 맨 마지막 노드까지 조회한 다음 해당 노드가 새로운 노드를 가리키도록 설정 
• get(self,idx): 특정 인덱스 값 가져오기
• insert_at(self, idx, value): 특정 위치에 값 추가
  • 새로운 노드를 생성한다.
  • 현재 idx 위치에 있는 노드가 가리키는 주소를 새로운 노드가 가리키게한다.
  • 원래 idx 위치에 있던 노드가 새로운 노드를 가리키게 한다.  
• remove_at(self, idx): 특정 위치 값 삭제 
  • 삭제할 위치에 있던 노드가 가리키는 노드를 직전노드가 가리키도록 수정한다. 

class LinkedList:
    def __init__(self):
        self.head = None
        
	## 맨 뒤에 데이터 추가하는 함수
    def append(self,value):
        new_node = Node(value)
        #처음 노드일때
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
	
    ## 특정 인덱스 값을 가져오는 함수 
    def get(self,idx):
        current = self.head
        for i in range(idx):
            current = current.next

        return current.value

	## 특정 위치에 값을 추가하는 함수
    def insert_at(self,idx, value):
        new_node = Node(value)
        current = self.head
        for i in range(idx-1):
            current = current.next

        new_node.next = current.next
        current.next = new_node
        
     ## 특정 위치의 값 삭제하는 함수
     def remove_at(self,idx):
        current = self.head
        target = self.head

		# current = 삭제할 노드
        for i in range(idx):
            current = current.next

		# target = 삭제할 노드의 직전 노드 
        for i in range(idx-1):
            target = target.next

		# 삭제할 노드의 직전 노드가 삭제할 노드의 다음 노드를 가리키도록 연결 수정 
        target.next = current.next

 

3) 연결리스트 사용하기

f = LinkedList() #객체 생성
f.append(1) # 노드 추가
f.append(2) # 노드 추가
f.append(3) # 노드 추가
f.append(4) # 노드 추가
value = f.get(2) # 특정 인덱스 값 가져오기
print(value) #  -> 3
f.insert_at(2,10) # 특정 인덱스에 값 추가하기 
value = f.get(2)  # 특정 인덱스 값 가져오기
print(value) # -> 10
f.remove_at(2) # 특정 인덱스 값 삭제
value = f.get(2) #특정 인덱스 값 가져오기
print(value) # -> 3

 

참고: 

•  https://www.geeksforgeeks.org/singly-linked-list-definition-meaning-dsa/