[알고리즘 강의] 파트7. 연결 리스트(Linked Lists) (1)

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

Data

• 정수, 문자열, 레코드, ...

A set of operations

• 삽입, 삭제, 순회, ...
• 정렬, 탐색, ...

 

기본적 연결 리스트

Node

 

• Node: Data + link (next)
• Node 내의 데이터는 다른 구조로 이루어질 수 있음 (예) 문자열, 레코드, 또 다른 연결 리스트 등
• 리스트의 맨 앞 노드: Head (위에선 67)
• 리스트이 맨 뒤 노드: Tail (위에선 58)
• # of nodes: 3

 

자료 구조 정의

Node

• Data
• Link (next)

# Node
class Node:
  def __init__(self,item):
    self.data = item #67
    self.next = None #다음 노드를 가리키는 포인터

 

비어 있는 연결 리스트

 

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

 

연산 정의

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

 

 

1. 특정 원소 참조

 

def 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
  return curr

 

배열과 비교한 연결 리스트

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

 

실습 과제 - 연결 리스트 순회

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

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

    def traverse(self):
        answer=[]
        i=1
        curr = self.head
        while i <= self.nodeCount:
            answer.append(curr.data)
            curr = curr.next
            i+=1
        return answer


# 이 solution 함수는 그대로 두어야 합니다.
def solution(x):
    return 0

 

* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.