python 자료구조 TIL (LinkedList)

오늘 실시간 강의에서 링크드리스트를 들었다!

 

참 지긋지긋하게도 여러번 들었던 링크드리스트..

 

학부생때는 C로 들었고,

독학할때는 java로 들었고,

내배캠에서는 python으로 듣게되었다

 

링크드리스트.. 이젠 진짜 익숙해진것같다

 

LinkedList

우선 기본적으로 두 개의 클래스를 선언해야 한다.

 

class Node():

    def __init__(self, data=None, data2=None): # 기본값 설정해주지 않아도 List 클래스에서 했기 때문에 괜찮음
        self.data = data
        self.data2 = data2
        self.next = None
        

class List():

    head = None # 이 줄도 안써도 됨

    def __init__(self, data=None, data2=None):
        self.head = Node(data, data2)

 

리스트의 각 노드가 될 클래스와, ( 여기선 Node 클래스 )

리스트 자체가 될 클래스. ( 여기선 List 클래스 )

 

 

 

 

.append() 끝 지점(tail 노드)에 노드 추가하기

맨 끝 지점에 요소를 추가할 메소드 append를 구현해보았다

 

def append(self, data=None, data2=None):

    if self.head is None: # 임의로 head를 None으로 만들었을 경우 예외처리
        print('리스트가 비어 있어 헤드를 생성하였습니다')
        self.head = Node(data, data2)
        return

    curr = self.head # head 부터 리스트를 돌기 위해 curr 라는 임시 노드에 head를 할당

    while curr.next is not None: # curr.next가 None이 아닐 때까지 (tail까지) 반복문으로 이동
        curr = curr.next

    curr.next = Node(data, data2) # tail의 next에 새로운 노드 추가 (새로운 노드를 만들고 next로 연결)

 

 

.getNode() 특정 노드 찾기

인덱스 기준으로 찾는 getNode() 메소드와 값 기준으로 찾는 getNodeWithValueInData() 메소드를 만들어 보았다

 

def getNode(self, idx):

    if self.head is None:
        print('현재 리스트가 비어있습니다')
        return

    elif idx < 0: # 잘못된 인덱스값 예외처리
        print('idx 값이 음수입니다. 잘못된 값')
        return

    curr = self.head
    cnt = 0;

    while curr.next is not None:

        if idx == cnt:
            return curr

        curr = curr.next
        cnt += 1

    return curr
    
    

def getNodeWithValueInData(self, value):

    if self.head is None:
        print('현재 리스트가 비어있습니다')
        return

    curr = self.head

    while curr.next is not None:

        if curr.data == value:
            return curr

        curr = curr.next

    print('찾는 값이 리스트에 없습니다')

    return

idx값 기준으로 찾는 getNode()는 idx가 리스트의 길이보다 클 경우엔 무조건 tail 노드를 반환하도록 했고,

 

getNodeWithValueInData() 는 data2 말고 data만 찾는 함수이다!

 

 

 

.addNode() 원하는 위치에 값 추가하기

 

def addNode(self, idx, data=None, data2=None):

    if self.head is None:
        print('리스트가 비어 있어 헤드를 생성하였습니다')
        self.head = Node(data, data2)
        return

    if idx == 0: #idx가 0으로 들어올 때, 헤드에 새로운 노드 추가
        temp = self.head
        self.head = Node(data, data2)
        self.head.next = temp
        return
        
    elif idx < 0:
        print('idx 값이 음수입니다. 잘못된 값')
        return



    curr = self.getNode(idx)
    prev = self.getNode(idx - 1)

    if curr == prev: 		# idx가 리스트의 길이보다 클 경우 예외처리. 본문에 서술
        curr.next = Node(data, data2) 	
                       
        return


    newNode = Node(data, data2)
    prev.next = newNode
    newNode.next = curr

    return

 

여기서 if curr == prev:  이 조건은 

idx가 리스트의 길이보다 크면 .getNode() 메소드가 무조건 tail을 반환하도록 했으므로,

이럴 경우 curr과 prev가 둘다 tail을 가르키는 문제가 생기고, 그럼 노드가 무한대로 생성되는 문제가 발생한다.

 

그것을 방지하기 위해 둘 다 tail을 가르키는 상황( 끝지점에 도달한 상황 )을 예외처리 한것!

 

 

.printAllNodes() 리스트 전체 출력하기

def printAllNodes(self):

    if self.head is None:
        print('리스트가 비어있습니다')
        return

    curr = self.head

    while curr.next is not None:
        print(curr.data, curr.data2)
        curr = curr.next

    print(curr.data, curr.data2)

    return

 

 

 

.deleteNode() 특정 노드 지우기

def deleteNode(self, idx):

    if idx == 0:
        self.head = self.head.next
        return

    elif idx < 0:
        print('idx값이 음수입니다')
        return

    curr = self.getNode(idx)
    prev = self.getNode(idx - 1)

    if curr == prev:
        # 여기가 문제..
        return

    prev.next = curr.next        

    return

지우는 메소드는.. 내가 .getNode()에서 idx가 리스트 길이보다 길 때 무조건 끝지점만 반환하도록 설계하는 바람에

끝부분을 지우려면 좀 번거로워진다.

 

리스트 길이를 반환하는 메소드를 만들든지,

Node 클래스에 prev를 추가해서 노드 추가할때마다 prev도 연결을 하든지.

getNode() 메소드 내부를 좀 바꾸든지..

 

이건 일단 보류하고 내일 해야겠다!!

 

 

 

 

지우는 메소드는 새로 짠 링크드리스트로!

 

2022.11.25 - [자료구조] - 알고리즘용 LinkedList

알고리즘용 LinkedList