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

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

---

연결 리스트(Linked Lists)

• 데이터 원소들을 순서를 지어 늘어놓는다
• 선형 배열(Linear array)와 비슷함
• 선형 배열 : 번호가 붙여진 칸(index)에 원소들을 채워넣어 관리하는 방식
• 연결 리스트 : 각 원소들을 줄줄이 엮어서 관리하는 방식

기본적 연결 리스트

• Node 내의 데이터는 다른 구조로 이루어질 수 있음
  e.g. 문자열, 레코드, 또 다른 연결 리스트

# 연결리스트 -> 코드로 표현
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

연산 정의

1. 특정 원소 참조(k 번째)

2. 리스트 순회

3. 길이 얻어내기

4. 원소 삽입

5. 원소 삭제

6. 두 리스트 합치기

---

특정 원소 참조

• K번째 원소를 찾기

# pos번째 노드 찾기 메소드
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

배열과 연결리스트 비교

[실습] 연결 리스트 순회

문제

어서와! 자료구조와 알고리즘은 처음이지? 7강 실습: 연결 리스트 순회

문제 설명

제 7 강에서 소개된 추상적 자료구조로 LinkedList 라는 이름의 클래스가 정의되어 있다고 가정하고, 이 리스트를 처음부터 끝까지 순회하는 메서드 traverse() 를 완성하세요.

메서드 traverse() 는 리스트를 리턴하되, 이 리스트에는 연결 리스트의 노드들에 들어 있는 데이터 아이템들을 연결 리스트에서의 순서와 같도록 포함합니다. 예를 들어, LinkedList L 에 들어 있는 노드들이 43 -> 85 -> 62 라면, 올바른 리턴 값은 [43, 85, 62] 입니다.

이 규칙을 적용하면, 빈 연결 리스트에 대한 순회 결과로 traverse() 메서드가 리턴해야 할 올바른 결과는 [] 입니다.

[참고] 실행 을 눌렀을 때 통과하는 것은 아무 의미 없습니다.

---

나의 풀이

• curr.head.data가 리턴되는 List에 append되어야함
• 따라서 현재 노드의 위치와 값을 구해야함
  • curr = self.head
  • data = curr.data
• 그리고 다음 위치를 curr에 넣음
  • curr = curr.next

solution.py

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):
        if not self.head:
            return []

        returnList = []
        curr = self.head # 1 

        while curr is not None:
            returnList.append(curr.data) # 67
            curr = curr.next
            
        return returnList

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

실행결과

정확성  테스트
테스트 1 〉	통과 (0.05ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.04ms, 10.8MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0