[Algorithm] 자료구조 - 연결 리스트 (Linked list)

2021. 3. 25. 02:11·Computer Science/Algorithm
728x90

 

연결 리스트 (Linked List)


각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 구조이다

데이터를 저장할 때 그 다음 순서의 데이터가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장

 

 

연결 리스트의 특징


- 동적 자료 구조

- 원소에 직접 접근할 수 없어서 배열보다 성능이 느리다

- 저장할 원소의 개수를 알지 못할 때 유용

- 종류 : 선형(linear), 원형(circular), 이중(doubly), 이중 원형(doubly circular) 등

💡 배열 : codesyun.tistory.com/107

 

[Algorithm] 배열(Array)

배열 같은 자료형의 다중 원소 집합 순서대로 번호(인덱스, index)가 붙은 원소들이 연속적인 형태로 구성되어 있다 배열의 사용과 시간복잡도 1. k번째 위치에 원소 삽입 : 상수 시간 O(1)에 k번째

codesyun.tistory.com

 

 

연결 리스트의 API와 시간복잡도

API (Application Programming Interface)


- Insert(k)

    * 리스트 맨 앞에 k를 추가하고 포인터를 이동

    * 새 원소는 리스트의 첫 번째 원소가 된다

    * 상수 시간 O(1) 에 수행된다

 

- Delete()

    * 리스트의 첫 번째 원소를 삭제

    * 리스트의 첫 번째 원소를 삭제하기 위해서는 포인터만 이동하면 된다

    * 상수 시간 O(1) 에 수행된다

 

- PrintList()

    * 리스트의 모든 원소를 표시

    * 첫 번째 원소부터 다음 포인터를 따라가며 표시

    * O(n) 시간에 수행된다

 

- Find(k)

    * 값이 k인 원소의 위치를 찾는다

    * 첫 번째 원소부터 찾는 값을 발견할 때 또는 리스트의 끝에 도달할 때까지 다음 포인터를 따라간다

    * O(n) 시간에 수행된다

 

- FindKth(k)

    * k번째 위치의 원소를 찾는다

    * 첫 번째 원소부터 k번째 원소에 도달할 때까지 다음 포인터를 따라간다

    * O(n) 시간에 수행된다

 

- IsEmpty()

    * 원소가 없는 빈 리스트인지 확인한다

    * 리스트의 헤드 포인터가 Null 값을 가지면 빈 리스트이다

    * O(1) 시간에 수행된다

 

 

 

💡 자료 구조 : codesyun.tistory.com/106

 

[Algorithm] 자료 구조(Data Structure) 란?

자료 구조(Data Structure) - 데이터의 구체적 표현이며, 데이터를 프로그래머 관점에서 정의한다 - 데이터를 메모리에 저장하는 방법을 나타낸다 - 문제 유형에 따라 최적의 자료 구조를 선택해야

codesyun.tistory.com

 

 

 

 

728x90
저작자표시 비영리 (새창열림)

'Computer Science > Algorithm' 카테고리의 다른 글

[Algorithm] 자료구조 - 큐 (Queue)  (0) 2021.03.25
[Algorithm] 자료구조 - 스택 (Stack)  (0) 2021.03.25
[Algorithm] 자료구조 - 배열(Array)  (0) 2021.03.25
[Algorithm] 자료구조(Data Structure) 란?  (0) 2021.03.25
[Algorithm] 빅오 표기법과 시간 복잡도의 개념 및 예제  (2) 2021.03.24
'Computer Science/Algorithm' 카테고리의 다른 글
  • [Algorithm] 자료구조 - 큐 (Queue)
  • [Algorithm] 자료구조 - 스택 (Stack)
  • [Algorithm] 자료구조 - 배열(Array)
  • [Algorithm] 자료구조(Data Structure) 란?
s_ih_yun
s_ih_yun
  • s_ih_yun
    CODESYUN
    s_ih_yun
  • 전체
    오늘
    어제
    • 분류 전체보기 (338) N
      • Web (8) N
      • Java (7) N
      • Spring (18) N
      • Git (16) N
      • MyBatis (1)
      • HTML & CSS (14)
      • JavaScript (11)
      • DevOps (4) N
      • Cloud (8)
      • Lanuage (13)
        • C++ (3)
        • Python (10)
      • DB (1) N
        • MySQL (1)
        • Oracle (2)
      • Computer Science (26)
        • Concept (3)
        • Algorithm (23)
      • Baekjoon (104)
        • 단계별로 풀어보기 (78)
      • CodeUp (98)
        • Python 기초 100제 (98)
      • Programmers (2)
      • Books (3)
      • etc (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

    • Syun's Pages
  • 인기 글

  • 태그

    clean code
    github
    VS Code
    codeup
    oracle
    HTML
    git
    java
    db
    자료구조
    aws
    spring
    Programmers
    JavaScript
    myBatis
    c++
    BOJ
    Python
    CodeUp 기초 100제
    Tistory
    SourceTree
    웹
    알고리즘
    단계별로 풀어보기
    MySQL
    Cloud
    CSS
    web
    C
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
s_ih_yun
[Algorithm] 자료구조 - 연결 리스트 (Linked list)
상단으로

티스토리툴바