[자료 구조]링크드 리스트(Linked List)

이도원·2022년 10월 19일
0

링크드리스트는 배열의 단점을 개선하기 위해 생긴 자료구조
C언어에서의 중요한 데이터 구조
파이썬은 자료형 중 리스트가 이 링크드리스트의 모든 기능을 지원

1. 장점

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

2. 단점

  • 배열은 인덱스를 통해 데이터에 접근하므로 시간복잡도 O(1)을 갖지만 링크드리스트의 경우 O(n)
  • 저장공간 효율이 높지 않음(데이터를 연결하기 위해선 별도의 주소 공간을 가짐)
  • 중간데이터를 삭제시, 앞뒤 데이터를 연결하고 재구성하는 코드가 추가로 필요

3. python code

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val # val은 현재값
        self.next = next # next 다음 
profile
studying

0개의 댓글