파이썬 자료구조 링크드 리스트(1)(단일)

우선 단일 링크드 리스트인을 연습삼아 구현하면서 링크드 리스드인 이해를 해보도록 하겠습니다.

대표적인 데이터 구조: 링크드 리스트(Linked List)

1. 링크드 리스트 (Linked List) 구조

• 연결리스트라고도 함.
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터구조.
• 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
• 본래 C언어에서는 주요한 데이터구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원
• 링크드 리스트 기본 구조와 용어
  • 노드(Node): 데이터 저장 단위로 구성(data,next)
  • 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간(주소값)
• 일반적인 링크드 링스트 형태

2. 링크드 리스트의 장단점(전통적인 C언어에서의 배열과 링크드 리스트의 관점에서)

• 장점

  • 미리 데이터 공간을 할당하지 않아도 됨
    • 배열은 미리 데이터 공간을 할당 해야함

• 단점

  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  • 중간 데이터 삭제 시, 앞뒤 데이터 연결을 재구성해야 하는 부가적인 작업 필요

  

출처(https://medium.com/wasd/c-c-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-1-41a312399a8f)

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

# 클래스로 노드생성 구현하기 (data,next)
# 클래스가 생성될때 __init__ 메소드가 실행 된다.

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
        
node1 = Node(1) // node1.data == 1 , node.next == None
node2 = Node(2)

# 두 노드를 이어줄려면 next값에 다음 노드를 가르키면 된다.

node1.next = node2

# 제일 앞노드 값은 무조건 알고 있어야 한다.
# head값에다가 할당

head = node1

# 링크드리스트에 데이터 추가하기 
# 제일 마지막값에 데이터를 추가해야 하므로 제일 마지막 노드를 알아야 한다.
# 링크드 리스트는 노드간에 연결이 되어 있고 제일 처음노드를 head변수에 할당에 했기 때문에 
# 반복문을 통해서 제일 마지막노드를 찾아보자

# 데이터 추가 함수
def add(data):
    # 제일 처음노드 찾기
    node = head # head에 제일 처음노드가 할당되어 있음
    
    while node.next: 
        # 만약 노드에 next값이 있을경우 => 다음값이랑 연결되어 있음
        # 만약에 노드의 next값이 null일 경우 제일 마지막 노드인걸 알수 있음
        
        node = node.next # node.next에 다음 노드값이 연결에 되어 있기때문에 node에 할당해준다.
    # 제일 마지막값이 node변수 저장 되어있고 node.next에 Node를 생성해서 넣어준다.
    # 제일 마지막 노드의 next에는 None이기 때문에
    node.next = Node(data) // Node가 하나 생성되고 node.next와 연결이 이루어짐

# 링크드리스트인 데이터 출력

def search():
    node = head
    while node.next:
        print(node.data)
        node = node.next
    print(node.data) # 제일 마지막 데이터 출력하기

add 함수와 비슷하다....


# 특정 노드 앞에 노드 삽입하기

node = head // 제일 처음 노드를 변수에 할당

# 특정노드를 찾으면 False로 변환
search = True

new_node = Node(1.5)

while search:
    if node.data == 1:
        search = False
    else:
        node = node.next

node_next = node.next # 현재 Node의 연결되어 있는 노드를 변수에 할당 => 나중에 쓰기위해
node.next = new_node # 삽입할 노드를 현재 노드의 next와 연결
node_next = new_node.next # 새롭게 삽입한 노드의 next의 값을 다음 Node와 연결

특정데이터 앞에 데이터 삽입

(출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)