4.1. 연결리스트

• 노드 : 연결리스트는 요소들이 참조로 이루어져 있고, 각 요소는 노드라는 틀에 담겨져 있음.
• 노드 구조

  • data : 실제 저장하려는 데이터
  • link : 다음 노드

1) 종류

• 단순 연결리스트 : 다음 노드를 가리키는 참조 하나만 가짐
• 이중 연결리스트 : 앞 노드와 뒷 노드를 가리키는 참조가 각각 존재

2) 연산

2-1) 삽입, 삭제 연산

• 성능 : O(1)
  ex) 1, 2, 3 중 1과 2 사이에 4 삽입 : 1의 link를 4로, 4의 link를 2로 연결
  ex) 1, 4, 2 중 4 삭제 : 1의 link를 2로 연결만 해주면 됨.
• 데이터 10만개가 있다고 가정했을 때, 동적 배열의 경우 데이터 중간 삽입, 삭제 시 10만번의 연산 필요함 : 동적 배열의 성능 O(n)

2-2) 탐색

• 성능 : O(n)
• cur 변수 : 노드의 첫 노드를 가리키게 함.
• cur 변수가 찾고자 하는 노드 값과 비교하면서 link를 통해 다음 노드로 넘어감 : 데이터 n개에 대하여 n번의 비교 필요
• 동적 배열의 경우, 해당 인덱스로 바로 접근이 가능함 : 성능 O(1)

4.2. 더미 이중 연결리스트

1) ADT

1-1) Object

• 순서 있는 유한 집합

1-2) Operation

1. empty() : Boolean 타입
2. size() : Integer 타입, 요소의 개수 반환
3. add_first(data) : data를 리스트 맨 앞에 추가
4. add_last(data) : data를 리스트 맨 마지막에 추가
5. insert_after(data, node) : data를 노드 다음에 삽입
6. insert_before(data, node) : data를 노드 이전에 삽입
7. search_forward(target) : node 반환, target을 리스트 맨 처음부터 찾아나가다가 리스트에 있으면 해당 노드 반환, 없으면 None 반환
8. search_backward(target) : node 반환, target을 리스트 맨 마지막부터 찾아나가다가 리스트에 있으면 해당 노드 반환, 없으면 None 반환
9. delete_first() : 리스트의 첫 번째 요소 삭제
10. delete_last() : 리스트의 마지막 요소 삭제
11. delete_node(node) : node 삭제

1-3) 구현

1) 노드

class Node():
    def __init__(self, data=None) -> None:
        self.__data = data
        self.__prev = None
        self.__next = None

    def __delete__(self):
        print("data of {} is deleted".format(self.data))
    # 소멸자 : 객체가 사라지기 전에 반드시 호출됨
    # 삭제 연산 시 삭제되는 것 확인하기 위한 코드

    def data(self):
        return self.__data
    #property
    def data(self, data):
        self.__data = data
    #data.setter

    def prev(self):
        return self.__prev
    #property
    def prev(self, p):
        self.__prev = p
    #prev.setter

    def next(self):
        return self.__next
    #property
    def next(self, n):
        self.__next = n
    #next.setter

• __init__ 생성자
  1) __data : 데이터를 저장
  2) __prev : 이전 노드 참조
  3) __next : 다음 노드 참조
• proptery를 통해 실제 변수 이름 대신 data, prev, next를 통해 접근 가능하도록 함.

2) DoubleLinkedList 정의

class DoubleLinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        # 더미 노드 : 맨처음과 맨끝 노드는 데이터를 저장하지 않음

        self.head.next = self.tail
        self.tail.prev = self.head
        #head, tail 연결
        
        self.d_size = 0
        # 데이터의 개수를 저장할 변수

• doubleLinkedList 클래스
  1) head : 리스트 맨 앞의 더미노드
  2) tail : 리스트 맨 뒤의 더미노드
  3) d_size : 리스트 내 데이터 개수

3) ADT 1,2 : empty(), size()

def empty(self):
        if self.d_size == 0:
            return True
        else : return False
    
    def size(self):
        return self.d_size

• empty() 메서드
• size() 메서드

4) ADT 3 : add_first()

def add_first(self, data):
        new_node = Node(data)
        new_node.next = self.head.next # 더미노드의 다음노드, 즉 첫번째 노드를 가리킴
        new_node.prev = self.head # prev는 리스트의 맨 앞 더미를 가리킴

        self.head.next.prev = new_node
        self.head.next = new_node
        
        self.d_size += 1   

• new_node = Node(data) : 새로운 노드 생성
  1) 새 노드의 prev와 next 연결
  -> 새로운 노드의 next가 현재 첫 번째 노드를 가리켜야 함.
  -> 이 때 참조값이 head.next : 첫 번째 노드에 대한 참조값임.
• new_node.next = self.head.next
  2) 현재 head.next가 첫 번째 노드이므로 새로운 노드의 뒤로 연결
• new_node.prev = self.head
  3) head를 새로운 노드의 prev와 연결함으로써 새로운 노드를 첫 번째 노드로 설정

-> 여기까지는 새로운 노드에서 각각 head와 첫 번째 노드를 단방향으로만 연결하였음

• self.head.next.prev = new_node
  4) 첫 번째 노드의 prev(self.head.next.prev)와 새로운 노드와 연결
• self.head.next = new_node
  5) 더미 노드인 head의 next를 새로운 노드와 연결

4) ADT 4 : add_last()

def add_last(self, data):
        new_node = Node(data)
        new_node.next = self.tail
        new_node.prev = self.tail.prev

        self.tail.prev = new_node
        self.tail.prev.next = new_node

        self.d_size += 1

• new_node = Node(data)
  1) 새 노드의 prev와 next 연결
  -> 새로운 노드의 next가 마지막 노드를 가리켜야 함.
  -> 이 때 참조값이 tail.prev : 마지막 노드에 대한 참조값.
• new_node.next = self.tail
  2) 새로운 노드는 마지막 노드이므로, 새로운 노드의 next는 tail과 연결됨
• new_node.prev = self.tail.prev
  3) tail.prev를 통해 현재 마지막 노드의 next 값을 얻어 new_node.prev와 연결.
• self.tail.prev = new_node
  4) tail의 prev에 새로운 노드 연결
• self.tail.prev.next = new_node
  5) 현재 마지막 노드의 값의 next에 새로운 노드를 연결함으로써 새로운 노드를 마지막 노드로 만듦

5) ADT 5 : insert_after()

def insert_after(self, data, node):
        new_node = Node(data)
        new_node.next = node.next
        new_node.prev = node

        node.next.prev = new_node
        node.next = new_node

        self.d_size += 1

• new_node = Node(data)
  1) 새 노드의 prev와 next 연결
  -> 기존 node값 다음에 새로운 노드 삽입
• new_node.next = node.next
  2) 새로운 노드의 next는 기존의 노드 next값이 됨
• new_node.prev = node
  3) 새로운 노드의 prev 값이 노드를 가리킴.
• node.next.prev = new_node
  4) node.next.prev, 즉 기존 노드의 다음 값은 새로운 노드와 연결
• node.next = new_node
  5) 현재 노드의 next를 새로운 노드와 연결

6) ADT 6 : insert_before()

def insert_before(self, data, node):
        new_node = Node(data)
        new_node.next = node
        new_node.prev = node.prev

        node.prev.next = new_node
        node.prev = new_node

        self.d_size += 1

• new_node = Node(data)
  1) 새 노드의 prev와 next 연결
  -> 기존 node값 바로 앞에 새로운 노드 삽입
• new_node.next = node
  2) 새로운 노드의 next는 기존의 노드가 됨
• new_node.prev = node.prev
  3) 새로운 노드의 prev 값이 기존 노드의 바로 앞 노드를 가리킴.
• node.prev.next = new_node
  4) node.prev.next, 즉 기존 노드의 이전 값과 새로운 노드와 연결
• node.prev = new_node
  5) 현재 노드의 prev를 새로운 노드와 연결

7) ADT 7, 8 : search_forward(), search_backward()

def search_forward(self, target):
        cur = self.head.next

        while cur is not self.tail :
            if cur.data == target :
                return cur
            cur = cur.next

        return None

def search_backward(self, target):
        cur = self.tail.prev

        while cur is not self.head :
            if cur.data == target :
                return cur
            cur = cur.prev

        return None
        

• cur = self.head.next
  1) head는 더미노드이므로 head 다음 노드가 데이터를 가진 첫 노드임.
  -> cur은 데이터를 가진 첫 노드부터 순회적으로 target 탐색
• while cur is not self.tail
  2) 더미노드가 나오기 전까지 데이터가 있는 노드로 간주함

9) ADT 9 : delete_first(), delete_last(), delete_node()

def delete_first(self):
        if self.empty():
            return
        self.head.next = self.head.next.prev
        self.head.next.prev = self.head

        self.d_size -= 1

• if self.empty(): return
  1) 만약 리스트에 노드가 없다면 함수 종료
• self.head.next = self.head.next.prev
  2) 첫 번째 데이터 노드 삭제이므로 head의 next는 두번째 노드와 연결해주어야 함.
  -> 두번째 노드는 self.head.next의 prev값으로 접근 가능
• self.head.next.prev = self.head
  3) 두 번째 노드의 prev값도 마찬가지로 head와 연결

def delete_last(self):
        if self.empty():
            return
        self.tail.prev = self.tail.prev.prev
        self.tail.prev.next = self.tail

        self.d_size -= 1

• self.tail.prev = self.tail.prev.prev
  1) 마지막 노드 삭제이므로 뒤에서 두번째에 위치한 노드와 tail값 연결
  -> tail.prev는 tail.prev(삭제예정인 노드)의 prev와 연결(뒤에서 두번째 노드)
• self.tail.prev.next = self.tail
  2) 위의 줄 실행 후, 뒤에서 두 번째 노드는 tail.prev이며, 이에 대한 next를 tail 과 연결

def delete_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

        self.d_size -= 1

• node.prev.next = node.next
  1) 삭제하고자 하는 값 : node이므로 node 기준 앞뒤로 연결해주면 됨
  -> node.prev는 노드의 바로 전 값이므로 그의 next값이 node의 next와 연결
• node.next.prev = node.prev
  2) node의 다음 값인 node.next의 prev도 마찬가지로 node의 전 노드와 연결