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

 

연결 리스트 (Linked List)

---

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

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

 

 

연결 리스트의 특징

---

- 동적 자료 구조

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

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

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

💡 배열 : codesyun.tistory.com/107

[Algorithm] 배열(Array)

 

 

연결 리스트의 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) 란?