[Python/파이썬] 자료구조 - 링크드리스트(Linked List) 1

 

  이번에는 링크드리스트(Linked List) 혹은 연결 리스트라고 불리우는 자료구조에 대해서 포스팅해보려 한다. 이전 배열 관련 포스팅에서는 배열은 인덱스를 통해 빠른 접근이 가능한게 장점이지만, 처음에 최대 크기를 정해놔야 해서 데이터를 추가/삭제하는 과정이 어렵다고 하였다.(파이썬 말고 C 해당)

(참고링크 :2021.05.23 - [코딩/Algorithm, 자료구조] - [Python/파이썬] 자료구조 - 배열(Array))

 

  링크드리스트는 배열의 단점을 개선하기 위해 생긴 자료구조라고 한다. 참고로 링크드리스트는 C언어에서의 중요한 데이터 구조였는데 파이썬은 자료형 중 리스트가 이 링크드리스트의 모든 기능을 지원한다.(배열 이어붙이기, 중간 삽입, 삭제 등)

 

 

 

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

 

  링크드리스트의 기본구조는 아래와 같다.

 

<링크드리스트 기본 자료구조>

-. Node : 데이터와 다음 데이터를 가리키는 주소(포인터)로 이루어져 있다.

-. Pointer : 각 노드에서 다음 데이터를 가리키는 주소값을 가진다.

-. Head : 링크드리스트에서 가장 시작점인 데이터를 의미한다.

-. Tail : 링크드리스트에서 가장 마지막 데이터를 의미

-. Next=None(또는 Null) : 다음 데이터가 없을 경우 포인터의 주소값은 None(또는 Null)이다.

 

 

 

2. 링크드리스트(Linked List) 장단점

 

  아래 장단점은 C언어에서의 장,단점이라고 이해하면 된다. 파이썬은 위에서 언급했지만 기본적으로 리스트 자료형이 링크드리스트의 모든 기능을 지원한다.

 

 

1) 장점

 

 -. 배열은 미리 데이터 공간을 할당해야 하지만 링크드리스트는 미리 할당할 필요가 없다.(유동적으로 데이터 추가,삭제 가능)

-.  링크드리스트 수정시 시간복잡도 O(1)을 갖는다. 

     : 항상 일정한 속도

 

2) 단점

 

-. 위 구조에서 보듯이 다음 데이터를 연결하기 위해선 별도의 주소 공간을 가져야 한다.

    : 저장공간 효율이 높지 않음

-. 배열은 인덱스를 통해 데이터에 접근하므로 시간복잡도 O(1)을 갖지만 링크드리스트의 경우 O(n)을 갖는다. 즉, 연결 된 정보를

찾기 위해 주소를 확인하고 다음 데이터를 탐색하는 시간이 있기 때문에 접근 속도가 느리다.

 -.  중간데이터를 삭제시, 앞뒤 데이터를 연결하고 재구성하는 코드가 추가로 필요하다.

 

 

 

3. 링크드리스트(Linked List) 파이썬 구현

 

  링크드리스트의 기본적인 기능(노드 구현 , 연결)에 대한 코드를 간단히 구현해본다. Node를 파이썬으로 구현하기 위해 Class를 먼저 선행해서 공부해야 한다. 

(참고링크 :  2021.03.14 - [코딩/Python] - [Python/파이썬] Class(클래스) 기초 정리 - 1 : 개념, 사용법)

 

 

1) Node 생성

 

<코드>

#Node 정의
class Node:
    def __init__(self, data, next=None):  #data 만 입력시 next 초기값은 None이다.
        self.data = data #다음 데이터 주소 초기값 = None
        self.next = next


#Node 생성해보기(data = 1)
node1 = Node(1)

#Node의 값과 포인터 출력하기
print(node1.data)
print(node1.next)

 

<결과>

1
None

 

 

2) Node 연결하기

 

<코드>

#Node1 생성해보기
node1 = Node(1)
#Node2 생성해보기
node2 = Node(3)
#Node 연결하기
node1.next = node2
#가장 맨 앞 Node를 알기 위해 head 지정
head = node1

#node1을 통해 연결한 결과 확인(밑에 2줄은 동일한 결과를 가리킨다)
print(node1.next.data)
print(node2.data)

 

<결과>

3
3

 

 

3) Node 뒤에 값(tail)을 추가하는 함수

 

<코드>

#Node 정의
class Node:
    def __init__(self, data, next=None):  #data 만 입력시 next 초기값은 None이다.
        self.data = data #다음 데이터 주소 초기값 = None
        self.next = next

def add(data):
    node = head
    while node.next: #node의 next가 있을 경우만 실행
        node = node.next #다음 노드가 있는지 계속 반복
    node.next = Node(data) #다음 노드가 없을 경우 루프를 빠져나와 새로운 노드 생성

#Node1 생성해보기
node1 = Node(1)
#가장 맨 앞 Node를 알기 위해 head 지정
head = node1
#add 함수 통해 신규 노드 추가하기
add(3)
#추가한 값을 node1 통해 next로 출력해보기
print(node1.next.data)

 

<결과>

1
3

 

 

4) Node 전체 출력해보기

 

<코드>

#Node1 생성해보기
node1 = Node(1)
#가장 맨 앞 Node를 알기 위해 head 지정
head = node1
#add 함수 통해 신규 노드 추가하기
add(3)
add(4)
add(5)

#추가한 값을 node1 통해 next로 출력해보기
node = head
while node.next: #node.next =None이 아닐 경우. 즉, node의 next가 있는 경우 실행
    print(node.data)
    node=node.next #node의 next가 없을 때까지 반복
print(node.data)

 

<결과>

1
3
4
5

 

  링크드리스트의 노드를 삭제하고 중간에 삽입하는 여러가지 기능은  다음편에 포스팅 할 예정

 

---

※ 참고자료 :  패스트 캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. 

자료구조 - 링크드리스트(LinkedList) 편

https://fastcampus.co.kr/dev_online_algo