0410_Data Structure /Linked List /Python / 클래스 구현

 

오랜만에 블로그를 쓴다. 며칠 만인지..

 

그 동안 web을 중점적으로 공부하느라 알고리즘에 소홀했는데 (시험 점수는 거짓말 하지 않지ㅠ) 앞으로 하루에 한문제씩은 알고리즘 문제를 풀면서 감을 챙길 생각이다. 어제 오늘 싸피에서 수업했던 내용은 바로 'Linked List'. 말은 쉽지만 코드로 구현해 내기까지 시간이 좀 걸렸다. 처음 과제로 받은 두 개의 문제 중 하나는 단순 리스트로 만들어서 풀었지만, 두 번째는 runtime error... 클래스 피해가려다 더 멀리 돌아가게 됐다ㅎ

 

사실 처음에는 class 정의해서 푸는 게 생각보다 복잡해 보이고(왜냐,, 나는 객체지향이 아직 낯설기 때문이다.) linked list에 대한 완벽한 이해도 되지 않은 상태라 도전할 엄두가 안 났지만, 과제는 해야겠고 앞으로 있을 코테도 걱정돼서 Data Structure에 대해, 특히 linked list 중점적으로 공부해봤다.

 

혹시라도 나와 같이 어려움을 겪는 사람들에게 조금이나마 도움이 됐으면 해서 내가 공부했던 순서를 간략히 남긴다.

 

공부 순서는

0. sw expert academy 강의 보기
1. 타 블로거님들의 자료도 읽어보고 위키피디아 참고
2. 생활코딩에서 데이터 스트럭쳐 중 linked list 자바로 설명해준 강의가 있다.
    물론 나는 자바를 몰라 앞에 개념 설명 위주로만 들었다. 감 잡기에는 아주 좋았다.
3. python으로 코드 구현하는 게 궁금했고, 덕봇기 오빠가 알려준 영상으로 코드 이해하고 연습해봄 
    유튜브에 python linked list를 검색해서 찾을 수 있는 영상- > 링크 참조 (https://youtu.be/JlMyYuY1aXU)
4. sw expert academy 관련 문제 풀이

 

 

---

<강의 들으면 정리한 내용>

 

- 노드와 헤드

노드 : 연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위

데이터 필드(원소 값 저장), 링크 필드(다음 노드 주소 저장)

헤드 : 리스트의 처음 노드를 가리키는 레퍼런스로, 데이터 값은 없다.

 

- 연결 리스트

• 단순 연결 리스트 : 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조, 헤드가 가장 앞의 노드, None을 가리키는 것이 가장 마지막 노드

- 이중 연결 리스트

• 두 개의 링크 필드와 한 개의 데이터 필드로 구성

• 삽입, 삭제

[생활코딩]

• linked list는 자료구조에서 가장 중요한 개념, 데이터 스트럭쳐에서 가장 중요한 목적은 메모리의 효율적 사용이다.

• 연결리스트에서는 각각의 엘리먼트는 노드로 나타낸다. 이때 노드는 데이터 필드(해당 노드에 담긴 value)와 링크 필드(다음 노드의 위치) 두 가지로 구성됩니다.

• array list 와 linked list를 비교하자면 (tade off 관계 따라서 상황에 맞추어 장단점을 비교해 사용해야 한다)

-> 추가/삭제에서는 linked list, 인덱스 조회에서는 array list가 빠르다.

 

-> linked는 리스트 크기가 확정적이지 않고 노드를 추가해서 무한히 늘릴 수 있다. 그러나 array는 정해진 리스트 크기가 있다. 공간의 낭비 등 비효율적인 것이 있음.

 

---

 

 

<클래스로 Linked List 코드_총 7개 method 구현>

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

    # 1.뒤에 노드 추가
    def append(self, data):
        new_node = Node(data)
        cur = self.head
        while cur.next!=None:
            cur = cur.next
        cur.next = new_node

    # 2. 리스트 길이 구하기
    def length(self):
        cur = self.head
        total = 0 #리스트 길이
        while cur.next!=None:
            total += 1
            cur = cur.next
        return total

    # 3. 전체 리스트 요소 보여주기
    def display(self):
        elems = []
        cur_node = self.head
        while cur_node.next!=None:
            cur_node=cur_node.next
            elems.append(cur_node.data)
        print(elems)

    # 4. 인덱스 위치의 노드 데이터 가져오기
    def get(self, index):
        if index >= self.length():
            # print("ERROR: 'GET' Index out of range!")
            return None
        cur_idx = 0
        cur_node = self.head
        while True:
            cur_node = cur_node.next
            if cur_idx == index:
                return cur_node.data
            cur_idx += 1

    # 5. 특정 인덱스의 노드 제거
    def erase(self, index):
        if index >= self.length():
            print("ERROR")
            return
        cur_idx = 0
        cur_node = self.head
        while True:
            last_node = cur_node
            cur_node = cur_node.next
            if cur_idx == index:
                last_node.next = cur_node.next #연결고리인 cur_node 없애기
                return
            cur_idx += 1

    # 6. 특정 인덱스에 노드 삽잎
    def add(self, index, data):
        if index >= self.length():
                # print("ERROR: 'add' Index out of range!")
                return
        new_node = Node(data)
        cur_idx = 0
        cur_node = self.head
        while True:
            last_node = cur_node
            cur_node = cur_node.next
            if cur_idx == index:
                last_node.next = new_node # last와 cur 사이에 new 삽입
                new_node.next = cur_node
                return
            cur_idx += 1

    # 7. 인덱스 위치 바로 다음 노드의 데이터 변경
    def change(self, index, data):
        if index >= self.length():
            print("ERROR:'Change' Index out of range!")
            return
        cur_idx = 0
        cur_node = self.head
        while True:
            last_node = cur_node
            cur_node = cur_node.next
            if cur_idx == index:
                cur_node.data = data
                last_node.next = cur_node
                return
            cur_idx += 1