6. 연결 리스트 (Linked Lists) (1)

추상적 자료구조 (Abstract Data Structures)

• Data
  • 예 : 정수, 문자열, 레코드, ...
• A set of operations
  • 삽입, 삭제, 순회 ...
  • 정렬,탐색

연결 리스트(Linked Lists)

연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식입니다, 이때 각각의 아이템(칸 하나)를 Node라고 부른다.

Node는 담은 데이터도 가지고 있지만 다음 노드가 어디있는지 링크데이터도 가지고있다.

리스트는 무조건 맨앞을 알아야하고 그것을 Head라고 부른다. 또한 리스트의 맨 끝 원소를 Tail이라고 부른다.

연결 리스트 안에 노드가 총 몇개 있는지 알고 있는것도 좋을 것.

ex 코드

    class LinkedList:
        def __init__(self): # 비어있는 연결 리스트 생성
            self.nodeCount = 0
            self.head = None
            self.tail = None

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

연산 정의

1. 특정 원소 참조(K번째) 
2. 리스트 순회 (연습문제)
3. 길이 얻어내기(연습문제
4. 원소 삽입 (다음 )
5. 원소 삭제 (다음 )
6. 두 리스트 합치기 (다음)

특정 원소 참조

#class LinkedList 의 매서드
    deef getAt(self,pos):
        if pos <= 0 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

배열과 비교한 연결 리스트

• 배열
  • 저장 공간 -> 연속한 위치
  • 특정 원소 지칭 -> 매우 간편 O(1)
• 연결 리스트
  • 저장 공간 -> 임의의 위치
  • 특정 원소 지정 -> 선형탐색과 유사 O(n)

연결 리스트의 단점

1. 선형 배열에 비해서 데이터 구조 표현에 소요되는 저장 공간 (메모리) 소요가 크다.
2. "k 번째의 원소"를 찾아가는 데에는 선형 배열의 경우보다 시간이 오래 걸린다.

장점은 다음글에 작성

본 작성 글은 어서와! 자료구조와 알고리즘은 처음이지? 강의를 보고 정리한 글입니다.