LinkedList

shin·2022년 6월 24일

Python DataStructure & Algorithm

목록 보기

2/16

1. 기본 LinkedList

1) Node & LinkedList 클래스

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 __repr__(self): # 연결리스트 객체 표현
        if self.nodeCount == 0:
            return 'LinkedList is empty'
        s = ''
        cur = self.head
        while cur is not None:
            s += repr(cur.data) # 객체를 문자열로 변환
            if cur.next is not None:
                s += ' -> '
            cur = cur.next
        return s

2) 특정 원소 참조 함수

    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

a = Node(32)
b = Node(58)
c = Node(10)
d = Node(74)

Create new LinkedList : LinkedList is empty

3) 노드 삽입 함수

    def insertAt(self, pos, newNode): # 새로운 노드 삽입
        if pos < 1 or pos > self.nodeCount + 1:
            return False
            
        if pos == 1: # 리스트 맨 앞에 삽입할 때 : O(1)
            newNode.next = self.head # 헤드 앞에 삽입
            self.head = newNode # 새로운 헤드로 지정
            
        else:
            if pos == self.nodeCount + 1:
                prev = self.tail # 이전 노드를 따로 찾을 필요 없음
            else:
                prev = self.getAt(pos - 1) # 이전 노드
            newNode.next = prev.next # prev와 prev.next 사이에 삽입 : O(n)
            prev.next = newNode
            
        if pos == self.nodeCount + 1: # 리스트 맨 뒤에 삽입할 때 : O(1)
            self.tail = newNode # 새로운 테일로 지정
        
        self.nodeCount += 1
        return True

L1.insertAt(1, a) : 32
L1.insertAt(1, b) : 58 -> 32
L1.insertAt(2, c) : 58 -> 10 -> 32
L1.insertAt(4, d) : 58 -> 10 -> 32 -> 74

4) 리스트 순회 함수

    def traverse(self): # 리스트 순회
            result = []
            curr = self.head
            while curr is not None:
                result.append(curr.data)
                curr = curr.next
            return result

L1.traverse() : [58, 10, 32, 74]

5) 노드 삭제 함수

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
            
        cur = self.getAt(pos)
        if pos == 1: # 맨 앞에서 삭제 : O(1)
            if self.nodeCount == 1: # 유일한 값을 삭제할 경우
                self.head = None
                self.tail = None
            else:
                self.head = cur.next
        else: # 중간, 맨 끝에서 삭제 : O(n)
            prev = self.getAt(pos - 1)
            prev.next = cur.next
            if pos == self.nodeCount:
                self.tail = prev
                
        self.nodeCount -= 1
        return cur.data

L1.popAt(1) : 58
L1 : 10 -> 32 -> 74
L1.popAt(2) : 32
L1 : 10 -> 74
L1.popAt(2) : 74
L1 : 10
L1.popAt(1) : 10
L1 : LinkedList is empty

2. dummy head 추가

1) LinkedList 초기화 함수 수정

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None) # 맨 앞에 dummy node 추가
        self.tail = None
        self.head.next = self.tail # 추가

2) traverse 함수 수정

    def traverse(self): # 리스트 순회
        result = []
        curr = self.head
        while curr.next: # 수정
            curr = curr.next
            result.append(curr.data)
        return result

3) getAt 함수 수정

    def getAt(self, pos): # 특정 원소 참조
        if pos < 0 or pos > self.nodeCount:
            return None
        i = 0 # getAt(0) -> head
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

4) insert 함수 수정

insertAfter 함수 활용해서 insertAt 코드를 간단하게 구현

     def insertAfter(self, prev, newNode): # 특정 노드 뒤에 삽입
        newNode.next = prev.next
        if prev.next is None: # 맨 마지막에 삽입하는 경우
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True
    
    def insertAt(self, pos, newNode): # 새로운 노드 삽입
        if pos < 1 or pos > self.nodeCount + 1:
            return False
            
        # empty node가 아니고 tail 뒤에 삽입하는 경우    
        if pos != 1 and pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)
         return curr

5) pop 함수 수정

popAfter 함수 활용해서 poptAt 코드를 간단하게 구현

    def popAfter(self, prev): # 특정 노드 뒤의 노드 삭제
        curr = prev.next
        if curr == None: # prev가 마지막 노드일 때
            return None
        if curr.next == None: # 리스트 맨 끝의 node를 삭제할 때
            self.tail = prev
        prev.next = curr.next
        self.nodeCount -= 1
        return curr.data
        
        
    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        prev = self.getAt(pos - 1)     
        return self.popAfter(prev)

6) concat 함수 수정

    def concat(self, L): # 두 리스트 연결   
        self.tail.next = L.head.next # 기존 리스트의 꼬리와 L의 머리 다음 노드를 연결
        if L.tail:
            self.tail = L.tail 
        self.nodeCount += L.nodeCount

3. Doubly LinkedLists

1) Node 초기화 함수 수정

class Node:
    def __init__(self, item):
        self.data = item
        self.prev = None # prev link 추가
        self.next = None

2) LinkedList 초기화 함수 수정

class DoublyLinkedList:
    def __init__(self):
        self.nodeCount = 0
        
        # 리스트 처음과 끝에 dummy node를 둠
        # 데이터를 담고 있는 node들은 모두 같은 모양이 됨
        self.head = Node(None)
        self.tail = Node(None)
        
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

3) repr 수정 및 getLength 함수 추가

     def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'
        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s

    def getLength(self):
        return self.nodeCount

3) 리스트 순회 함수 수정

    def traverse(self): # 리스트 순회
        result = []
        curr = self.head
        while curr.next.next: # dummy tail이 있기 때문에
            curr = curr.next
            result.append(curr.data)
        return result

4) 리스트 역순회 함수 추가

    def reverse(self): # 리스트 역순회
        result = []
        curr = self.tail
        while curr.prev.prev: # dummy head가 있기 때문에
            curr = curr.prev
            result.append(curr.data)
        return result

5) getAt 함수 수정

    def getAt(self, pos): # 특정 원소 참조
        if pos < 0 or pos > self.nodeCount:
            return None
        
        if pos > self.nodeCount // 2: # 후반부에 위치할 때
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1
        return curr

6) insert 함수 수정 및 insertBefore 함수 추가

    def insertAfter(self, prev, newNode): # 특정 노드 뒤에 삽입
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True
    
    
    def insertBefore(self, next, newNode): # 특정 노드 앞에 삽입
        prev = next.prev
        return insertAfter(prev, newNode)
    
    
    def insertAt(self, pos, newNode): # 지정된 위치에 새로운 노드 삽입
        if pos < 1 or pos > self.nodeCount + 1:
            return False
            
        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)

7) pop 함수 수정 및 popBefore 함수 추가

    def popAfter(self, prev): # 특정 노드의 다음 노드 삭제
        curr = prev.next
        prev.next = curr.next
        curr.next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popBefore(self, next): # 특정 노드의 이전 노드 삭제
        curr = next.prev
        next.prev = curr.prev
        curr.prev.next = next
        self.nodeCount -= 1
        return curr.data
        
        
    def popAt(self, pos): # 지정된 위치의 노드 삭제
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        prev = self.getAt(pos - 1)     
        return self.popAfter(prev)

8) 두 리스트 병합 함수 수정

    def concat(self, L): # 두 리스트 병합  
        self.tail.prev.next = L.head.next # 원래 리스트의 더미 꼬리를 L의 맨 앞 데이터 노드로 설정
        L.head.next.prev = self.tail.prev # prev 설정
        self.tail = L.tail # 전체 노드의 꼬리를 L의 꼬리로 설정
        self.nodeCount += L.nodeCount

출처 : 어서와! 자료구조와 알고리즘은 처음이지? - 프로그래머스

shin

Backend development

이전 포스트

정렬/탐색/재귀 알고리즘

다음 포스트

LinkedList

Python DataStructure & Algorithm

1. 기본 LinkedList

1) Node & LinkedList 클래스

2) 특정 원소 참조 함수

3) 노드 삽입 함수

4) 리스트 순회 함수

5) 노드 삭제 함수

2. dummy head 추가

1) LinkedList 초기화 함수 수정

2) traverse 함수 수정

3) getAt 함수 수정

4) insert 함수 수정

5) pop 함수 수정

6) concat 함수 수정

3. Doubly LinkedLists

1) Node 초기화 함수 수정

2) LinkedList 초기화 함수 수정

3) repr 수정 및 getLength 함수 추가

3) 리스트 순회 함수 수정

4) 리스트 역순회 함수 추가

5) getAt 함수 수정

6) insert 함수 수정 및 insertBefore 함수 추가

7) pop 함수 수정 및 popBefore 함수 추가

8) 두 리스트 병합 함수 수정

정렬/탐색/재귀 알고리즘

Stack

0개의 댓글

LinkedList

Python DataStructure & Algorithm

1. 기본 LinkedList

1) Node & LinkedList 클래스

2) 특정 원소 참조 함수

3) 노드 삽입 함수

4) 리스트 순회 함수

5) 노드 삭제 함수

2. dummy head 추가

1) LinkedList 초기화 함수 수정

2) traverse 함수 수정

3) getAt 함수 수정

4) insert 함수 수정

5) pop 함수 수정

6) concat 함수 수정

3. Doubly LinkedLists

1) Node 초기화 함수 수정

2) LinkedList 초기화 함수 수정

3) __repr__ 수정 및 getLength 함수 추가

3) 리스트 순회 함수 수정

4) 리스트 역순회 함수 추가

5) getAt 함수 수정

6) insert 함수 수정 및 insertBefore 함수 추가

7) pop 함수 수정 및 popBefore 함수 추가

8) 두 리스트 병합 함수 수정

정렬/탐색/재귀 알고리즘

Stack

0개의 댓글

3) repr 수정 및 getLength 함수 추가