알고리즘 기초 - Linked List

🌈 Linked List

🔥 연결 리스트(Linked List) 란?

🔥 연결 리스트 예시

🔥 객체지향 프로그래밍으로 연결 리스트 구현

🔥 연결 리스트 삭제 메서드 추가

🔥 이중 연결 리스트(Double linked list) 란?

1. 연결 리스트(Linked List) 란?

• 분리된 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조를 연결 리스트라함
• python에서는 list 타입에서 연결 리스트 기능을 모두 지원함
• 연결 리스트 기본 구조와 용어
  • 노드(Node) : 데이터 저장 단위(데이터값, 포인터)로 구성
  • 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
• 즉, 연결 리스트는 일반 배열과 달리 데이터 뿐 아니라 다음 데이터를 가르키는 주소(포인터)를 함께 가지고 있음

2. 연결 리스트 예시

1. 기본 연결리스트

• 연결 리스트는 데이터와 pointer가 Node로 구성되어 있기 때문에 이를 class 속성으로 구현 가능
• 연결된 리스트가 없는 경우(노드가 1개 뿐이거나, 마지막 노드인 경우)에 pointer 값은 None을 가짐
• 연결 리스트는 맨 첫번째 노드만 알면, 모든 노드를 확인할 수 있기 때문에 맨 앞에 노드를 head에 저장

class Node:
    def __init__(self, data, next=None): # 데이터, pointer
        self.data = data
        self.next = next
# 노드 생성
node1 = Node(11)
node2 = Node(22)
node3 = Node(33)
# 노드 연결
node1.next = node2 # 연결
node2.next = node3 # 연결
# 노드 출력 : 가장 앞에 있는 주소를 알기 위해 맨 앞의 노드를 head에 저장
head = node1
node = head
while node.next: # pointer가 있다면, 반복
    print(node.data) # 11, 22 
    node = node.next
print(node.data) # 33

2. 추가된 node 마지막에 삽입하여 연결하는 방법

• add 함수를 통해 node 생성 및 연결 방법 : 맨 첫 node부터 next를 반복하여, pointer(node.next)가 없다면, 현재의 pointer를 새로운 데이터와 연결

# 연결 리스트 생성
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
# Node 추가 함수 생성
def add(data):
        node = head
        while node.next: # = node1.next부터 시작
            node = node.next # pointer가 none일 때 까지 계속 진행
        node.next = Node(data) # 마지막 node에 데이터 삽입
# 맨 첫 노드 생성
node1 = Node(0)
head = node1
# 1~9까지 노드 추가
for i in range(1,10):
    add(i)
node = head
while node.next:
    print(node.data) # 0, 1, 2, 3, 4, 5, 6, 7, 8 
    node = node.next
print(node.data) # 9

3. 추가된 node 중간에 삽입 방법

• 노드 중간에 삽입하려면, 추가할 위치를 찾은 뒤 새로운 값을 연결시켜주고 그 새로운 값의 pointer에 다시 그 다음 노드의 값을 연결시켜줘야함
• 추가할 node의 pointer를 새로운 값을 가르키게하기기 전, 기존 node가 갖고 있던 pointer값을 다른 변수에 담아두었다가 새로운 값 연결 후, 그 새로운 값에 연이어 연결시켜주는 로직

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
# Node 추가 함수 생성
def add(data):
        node = head
        while node.next: # = node1.next부터 시작
            node = node.next # pointer가 none일 때 까지 계속 진행
        node.next = Node(data) # 마지막 node에 데이터 삽입
# 맨 첫 노드 생성
node1 = Node(0)
head = node1
# 1~9까지 기존 노드 생성
for i in range(1,10):
    add(i)
# 노드 삽입
node3 = Node(1.5)
node = head
# 노드 추가할 위치 찾기
search = True
while search:
    if node.data == 1: # node의 값이 1라면,
        search = False
    else:
        node = node.next
node_next = node.next # 현재 node.next는 데이터2를 가진 노드를 가르킴
node.next = node3 
node3.next = node_next
# 노드 출력
node = head
while node.next:
    print(node.data) # 0, 1, 1,5, 2, 3, 4, 5, 6, 7, 8 
    node = node.next
print(node.data) # 9

3. 객체지향 프로그래밍으로 연결 리스트 구현

• class Node는 노드 속성을 갖고 있고, class NodeMamt에서는 메서드를 통해 node를 관리함
• add 메서드를 통해 haed 값이 아직 존재하지 않을 때에는 맨 첫번째 추가된 노드를 haed에 담을 수 있게 해두고, head가 있다면 마지막 노드의 pointer(node.next)에 추가되는 노드를 연결

# 노드 생성
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
# 노드 관리
class NodeMgmt:
    def __init__(self, data): # head
        self.head = Node(data)
    def add(self, data): # 노드 추가
        if self.head == '': # head가 없으면, 맨 처음 추가된 노드가 head가 됨
            self.head = Node(data)
        else: # 추가될 때마다 노드를 연결시킴
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data) # 마지막 노트(node.next가 없는)에 새로운 노트 연결
    def desc(self): # 노드 출력
        node = self.head
        while node: # node를 head부터 시작해서 계속 출력
            print(node.data)
            node = node.next
# 연결 리스트 생성
linkedlist1 = NodeMgmt(0)
linkedlist1.desc() # 0
for data in range(1,10):
    linkedlist1.add(data)
linkedlist1.desc() # 0 1 2 3 4 5 6 7 8 9   

4. 연결 리스트 삭제 메서드 추가

• 노드를 지운다는 것을 4가지의 경우의 수를 가짐
  • node가 없는데 node 삭제를 요청 할 경우 : node가 없음을 출력함
  • haed를 지우는 경우 : 임시값에 삭제할 Node인 head를 보관 ⇢ head의 다음 Node를 head로 교체 ⇢ 임시값에 저장된 원래 head를 삭제
  • 중간 node를 지우는 경우 : 삭제할 node인 node.next를 찾기 ⇢ 삭제할 현재 노드(node.next)를 임시 값에 보관 ⇢ 현재 node(node.netx)를 다음 노드로 교체 ⇢ 임시값 삭제
  • 마지막 node를 지우는 경우 : 위와 동일

    def delete(self, data):
        if self.head == '':
            print('Empty Node')
        if self.head.data == data: # head를 삭제할 경우
            temp = self.head # 현재 head를 임시 값에 저장함
            self.head = self.head.next # 헤드의 다음 노드를 head로 변경
            del temp # 임시값 삭제
        else: # 중간 node 삭제할 경우
            node = self.head
            while node.next:
                if node.next.data == data: # 현재 node가 가르키는 node의 데이터 값이 삭제할 값이라면
                    temp = node.next # 삭제할 값을 temp에 넣음
                    node.next = node.next.next # 현재 node를 다음 node로 수정
                    del temp
                else:
                    node = node.next

• 삭제 예시

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
# 노드 관리
class NodeMgmt:
    def __init__(self, data): # head
        self.head = Node(data)
    def add(self, data): # 노드 추가
        if self.head == '': # head가 없으면, 맨 처음 추가된 노드가 head가 됨
            self.head = Node(data)
        else: # 추가될 때마다 노드를 연결시킴
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data) # 마지막 노트(node.next가 없는)에 새로운 노트 연결
    def desc(self): # 노드 출력
        node = self.head
        while node: # node를 head부터 시작해서 계속 출력
            print(node.data)
            node = node.next
    def delete(self, data): # 노드 삭제
        if self.head == '':
            print('Empty Node')
        if self.head.data == data: # head를 삭제할 경우
            temp = self.head # 현재 head를 임시 갑셍 저장함
            self.head = self.head.next # 헤드의 다음 노드를 head로 변경
            del temp # 임시값 삭제
        else: # 중간 node 삭제할 경우
            node = self.head
            while node.next:
                if node.next.data == data: # 현재 node가 가르키는 node의 데이터 값이 삭제할 값이라면
                    temp = node.next # 삭제할 값을 temp에 넣음
                    node.next = node.next.next # 현재 node를 다음 node로 수정
                    del temp
                else:
                    node = node.next
# 연결 리스트 생성(0~10)
linkedlist1 = NodeMgmt(0)
for data in range(1,10):
    linkedlist1.add(data)
# haed 지우기
linkedlist1.delete(0)
linkedlist1.desc() # 1 2 3 4 5 6 7 8 9
# 중간 node 지우기
linkedlist1.delete(5)
linkedlist1.desc() # 1 2 3 4 6 7 8 9
# 마지막 node 지우기
linkedlist1.delete(9)
linkedlist1.desc() # 1 2 3 4 6 7 8    

5. 이중 연결 리스트(Double linked list) 란?

• 노드가 10000개일 때, 8000번째 노드를 찾으려면 head부터 7999번 이동 해야하는 비효율성이 존재함
• 뒤에서 부터 역순으로 노트를 탐색하기 위해 고안된 것이 이중 연결 리스트임
• 이에 이중 연결 리스트는 각 노드마다 이전 데이터 주소, 데이터, 다음 데이터 주소를 갖음
• 이중 연결 리스트는 head와 tail을 가지고, 연결 주소도 next(다음)와 prev(이전)를 가짐

1) 이중 연결 리스트 기본 구조

class Node:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next
class NodeMgmt:
    # head, tail 세팅
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head
    # 데이터 삽입
    def insert(self, data):
        if self.head == None: # head가 없을 때,
            self.head = Node(data)
            self.tail = self.head
        else: # head가 이미 있을 때,
            node = self.head
            while node.next: # 마지막 노드 찾기
                node = node.next
            new = Node(data) # 추가된 객체 생성
            node.next = new # 마지막 노드와 추가된 객체 연결
            new.prev = node # 추가된 객체의 이전 노드를 현재 노드로 연결
            self.tail = new # 연결 리스트의 마지막을 현재 추가된 노드로 세팅
    # 데이터 출력
    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next
# 데이터 생성 : 0~10
double_linked_list = NodeMgmt(0)
for data in range(1,10):
    double_linked_list.insert(data)
double_linked_list.desc() # 0 1 2 3 4 5 6 7 8 9

2) 이중 연결 리스트 검색 기능 추가

• 이중 연결 리스트에서 검색 기능은 head부터 찾는 매서드와 tail부터 찾는 메서드로 구현

class Node:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next
class NodeMgmt:
    # head, tail 세팅
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head
    # 데이터 삽입
    def insert(self, data):
        if self.head == None: # head가 없을 때,
            self.head = Node(data)
            self.tail = self.head
        else: # head가 이미 있을 때,
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new
    # 데이터 출력
    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next
    # 검색 기능
    def search_form_head(self, data):
        if self.head == None:
            return False
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next
        return False
    def search_form_tail(self, data):
        if self.tail == None:
            return False
        node = self.tail
        while node:
            if node.data == data:
                return node
            else:
                node = node.prev
        return False    
# 데이터 생성 : 0~10
double_linked_list = NodeMgmt(0)
for data in range(1,10):
    double_linked_list.insert(data)
double_linked_list.desc() # 0 1 2 3 4 5 6 7 8 9
get_data_head = double_linked_list.search_form_head(3) 
if get_data_head:
    print(get_data_head.data) # 3
else:
    print(None)
get_data_tail = double_linked_list.search_form_tail(8) 
if get_data_tail:
    print(get_data_tail.data) # 8
else:
    print(None)

3) 이중 연결 리스트 중간 삽입 기능 추가

class Node:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next
class NodeMgmt:
    # head, tail 세팅
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head
    # 데이터 삽입
    def insert(self, data):
        if self.head == None: # head가 없을 때,
            self.head = Node(data)
            self.tail = self.head
        else: # head가 이미 있을 때,
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new
    # 데이터 출력
    def desc(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next
    # 검색 기능
    def search_form_head(self, data):
        if self.head == None:
            return False
        node = self.head
        while node:
            if node.data == data:
                return True
            else:
                node = node.next
        return False
    def search_form_tail(self, data):
        if self.tail == None:
            return False
        node = self.tail
        while node:
            if node.data == data:
                return True
            else:
                node = node.prev
        return False  
    # data = 1.5 / brfore_data = 2    
    def insert_before(self, data, before_data): 
        if self.head == None:
            self.head = Node(data)
            return True
        else:
            node = self.tail
            while node.data != before_data: # node값이 before_data와 같으면 종료
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            # node가 2이기 때문에, node.prev는 2를 가진 node의 이전 node를 가르킴
            before_new = node.prev 
            # before_new는 Node(1)이고, before_new의 next로 추가할 node를 연결
            before_new.next = new
            # 추가한 노드의 이전 노드는 Node(1)을 연결시킴
            new.prev = before_new
            # 현재 node값은 새로 추가한 node 다음으로 연결
            new.next = node
            # 현재 node의 이전 노드는 새로 추가한 노드로 연결
            node.prev = new
            return True
# 데이터 생성 : 0~10
double_linked_list = NodeMgmt(0)
for data in range(1,10):
    double_linked_list.insert(data)
double_linked_list.desc() # 0 1 2 3 4 5 6 7 8 9
double_linked_list.insert_before(1.5, 2)
double_linked_list.desc() # 0 1 1.5 2 3 4 5 6 7 8 9