Data Structure(1) Linked List (연결 리스트)

📌Linked List (연결 리스트)

• linked list는 떨어진 곳에 존재하는 데이터들을 포인터로 '연결'해서 관리하는 data structure
• 장점(배열의 단점 극복): 비연속적 데이터를 포인터로 연결하기 때문에 메모리를 미리 할당받을 필요가 없음
  배열은 연속적으로 연결된 공간에 데이터를 나열하기 때문에 특정한 연결된 공간을 미리 할당받아야 함
• 단점: 각 데이터마다 다음 노드를 가리키는 주소(포인터)도 같이 저장해야하므로 저장공간 효율↓
  첫 노드(head)부터 쭈우우-욱 검색해야 해서 연결 정보를 찾는 시간이 필요하여 데이터에 접근하는데에 시간이 소요 (배열은 index로 바로 접근 가능)
  중간에 데이터를 추가/삭제할 때, 추가적 작업이 필요

📌일반(간단한) linked list

1) node 구현

python class를 이용하여 linked list node 구현

class Node:  
def **init**(self, data):  
self.data = data  
self.next = None  

__init__함수로 클래스가 객체화 될 때마다 객체의 data와 next를 initialize
객체화 될 때마다 next는 None으로 선언

def **init**(self, data, next=None):  
self.data = data  
self.next = next  

instance를 생성할 때마다 parameter를 2개 넣을 수 있으며, 바로 next를 설정 가능(next 값 선언하지 않으면 default값은 None값으로)

2) node와 node 연결(pointer)

node2 = Node(2) #node2.data = 2, node2.next = None  
node1.next = node2  
head = node1  

3) 데이터 추가하기

def **init**(self, data, next=None):  
self.data = data  
self.next = next

def add(data):  
node = head #헤드 값 가져오기(node = head = node1 = Node(1))  
while node.next: #다음 노드가 있으면(node.next가 있으면)  
node = node.next #다음 노드로 이동 (마지막 노드까지 타기)  
node.next = Node(data) #마지막 노드의 next에 새로운 노드 할당  

• 데이터를 추가하는 함수 add() 정의
• while문은 다음 노드가 존재할 때까지 반복
  node를 계속 다음 node로 옮겨가며 결국 가장 마지막 node를 찾을 때까지 반복
• 마지막 노드를 찾으면 그 마지막 노드의 다음 주소를 새롭게 추가하고자 하는 객체 Node(data)로 할당

head = node1  
for index in range(2, 10):  
add(index)  

1부터 9까지 연결된 linked list 생성

4) 데이터 출력하기 (search)

node = head  
while node.next:  
print(node.data)  
node = node.next #다음 노드 타기  
print (node.data) #node.next가 없는 가장 마지막 node까지 출력 완료  

📌파이썬 객체지향 프로그래밍으로 linked list 구현

구현할 class: Node, NodeMgmt

구현할 function(method): add, desc, delete, search_node

1) node와 node 사이에 새로운 node 추가

(출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)

class Node:  
def **init**(self, data, next=None):  
self.data = data  
self.next = next

class NodeMgmt:  
def **init**(self, data):  
self.head = Node(data)


def add(self, data):
    if self.head == '': #방어코드
        self.head = Node(data)
    else:
        node = self.head
        while node.next: #while문은 제일 마지막 node를 타기 위함
            node = node.next
        node.next = Node(data)

def desc(self):
    node = self.head
    while node: #node가 있으면
        print (node.data)
        node = node.next #다음 node 타기

• NodeMgmt class에서는 __init__함수에서 NodeMgmt(data)를 객체화하여 instance를 생성하면 Node(data)가 head로 같이 생성됨
  (맨 앞 노드(head node)의 주소를 알고 있어야 전체 연결 리스트를 제어 가능(추가/삭제/검색))
• add(): 맨 끝에 노들ㄹ 추가하는 함수
• desc(): 전체 linked list의 값을 출력해주는 함수

```

linkedlist1 = NodeMgmt(0)
print(linkedlist1.desc()) #0
```

객체 생성 => data = 0, next = None, head = linkedlist1

for data in range(1, 10):  
linkedlist1.add(data)  
print(linkedlist1.desc()) #0, 1, 2, 3, 4, 5, 6, 7, 8, 9  

2) 특정 노드 삭제 (head node / tail node / middle node 삭제)

class Node:  
def **init**(self, data, next=None):  
self.data = data  
self.next = next

class NodeMgmt:  
def **init**(self, data):  
self.head = Node(data)


def add(self, data):
    if self.head == '':
        self.head = Node(data)
    else:
        node = self.head
        while node.next:
            node = node.next
        node.next = Node(data)

def desc(self):
    node = self.head
    while node:
        print (node.data)
        node = node.next

def delete(self, data):
    if self.head == '': #방어 코드: head가 아예 없을 때
        print ("해당 값을 가진 노드가 없습니다.")
        return

    if self.head.data == data: #head node를 삭제할 때
        temp = self.head
        self.head = self.head.next #head 변경
        del temp
    else: # middle/tail node를 삭제하는 경우
        node = self.head
        while node.next:
            if node.next.data == data: # if-else문은 내가 삭제하고자 하는 값을 찾을 때까지 반복
                temp = node.next
                node.next = node.next.next
                del temp
                return
            else: #내가 찾는 값이 아니면 다음 노드 타기
                node = node.next

• delete(): 특정 data를 가진 노드를 삭제하는 함수
• head node를 삭제하는 경우와 중간/tail node를 삭제하는 경우를 분리

3) 노드 데이터가 특정 숫자인 노드를 search

class Node:  
def **init**(self, data):  
self.data = data  
self.next = None

class NodeMgmt:  
def **init**(self, data):  
self.head = Node(data)


def add(self, data):
    if self.head == '':
        self.head = Node(data)
    else:
        node = self.head
        while node.next:
            node = node.next
        node.next = Node(data)

def desc(self):
    node = self.head
    while node:
        print (node.data)
        node = node.next

def delete(self, data):
    if self.head == '':
        print ('해당 값을 가진 노드가 없습니다.')
        return
    if self.head.data == data: # 경우의 수1: self.head를 삭제해야할 경우 - self.head를 바꿔줘야 함
        temp = self.head # self.head 객체를 삭제하기 위해, 임시로 temp에 담아서 객체를 삭제했음
        self.head = self.head.next # 만약 self.head 객체를 삭제하면, 이 코드가 실행이 안되기 때문!
        del temp
    else:
        node = self.head
        while node.next: # 경우의 수2: self.head가 아닌 노드를 삭제해야할 경우
            if node.next.data == data:
                temp = node.next
                node.next = node.next.next       
                del temp                         
                pass                             
            else:
                node = node.next

def search_node(self, data):
    node = self.head
    while node:
        if node.data == data:
            return node
        else:
            node = node.next

• search_node(): 특정 값을 가진 node를 search하는 함수

# test

node\_mgmt = NodeMgmt(0)  
for data in range(1, 10):  
node\_mgmt.add(data)

node = node\_mgmt.search\_node(4)  
print (node.data)  

📌Doubly Linked List

(출처: wikipedia, https://en.wikipedia.org/wiki/Linked_list)

• 이중 연결 리스트
• 양방향 연결 -> 양쪽으로 노드 탐색이 가능하여 더 효율적으로 탐색 가능
  (single linked list라면 head부터 한 방향으로 찾아가야 하지만, 찾고자 하는 데이터의 대략적인 위치를 안다면 head와 tail 양쪽에서 모두 탐색이 가능하기 때문에 효율적!)

1) doubly linked list 구현

def **init**(self, data, prev=None, next=None):  
self.prev = prev  
self.data = data  
self.next = next

class NodeMgmt:  
def **init**(self, data):  
self.head = Node(data)  
self.tail = self.head


def insert(self, data):
    if self.head == None:
        self.head = Node(data)
        self.tail = self.head #처음에는 node가 1개니까 head랑 tail이랑 똑같음
    else:
        node = self.head
        while node.next:
            node = node.next
        new = Node(data) #insert할 노드를 new라는 변수에 할당
        node.next = new
        new.prev = node
        self.tail = new #insert한 노드가 tail

def desc(self):
    node = self.head
    while node:
        print (node.data)
        node = node.next

• Node instance는 이전 노드 주소(prev)와 다음 노드 주소(next)를 가지고 있음
• insert(): 가장 끝에 node를 추가하는 함수
  node.next = new, new.prev = node가 핵심!!: 원래 노드는 다음 노드는 새로우 ㄴ노드를, 새로운 노드의 이전 노드는 원래 노드를

#test  
double\_linked\_list = NodeMgmt(0)  
for data in range(1, 10):  
double\_linked\_list.insert(data)  
double\_linked\_list.desc()  

2) 특정 노드 search (head부터 / tail부터)

def **init**(self, data, prev=None, next=None):  
self.prev = prev  
self.data = data  
self.next = next

class NodeMgmt:  
def **init**(self, data):  
self.head = Node(data)  
self.tail = self.head


def insert(self, data):
    if self.head == None:
        self.head = Node(data)
    else:
        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_from_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_from_tail(self, data):
    if self.head == None:
        return False

    node = self.tail #tail에서 부터 search
    while node:
        if node.data == data:
            return node
        else:
            node = node.prev
    return False

• search_from_head(): head부터 search하는 함수
• search_from_tail(): tail부터 search하는 함수

3) 노드 데이터가 특정 숫자인 노드 앞 / 뒤에 데이터 추가

class Node:  
def **init**(self, data, prev=None, next=None):  
self.prev = prev  
self.data = data  
self.next = next

class NodeMgmt:  
def **init**(self, data):  
self.head = Node(data)  
self.tail = self.head


def insert(self, data):
    if self.head == None:
        self.head = Node(data)
    else:
        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 insert_before(self, data, before_data):
    if self.head == None: #방어코드: head node가 없으면 바로 node instance 만들어주기
        self.head = Node(data)
        return True            
    else:
        node = self.tail
        while node.data != before_data: #내가 찾는 값을 찾을 때까지 반복
            node = node.prev
            if node == None: #내가 찾는 값이 없음
                return False
        new = Node(data) #일치하는 값을 찾으면 삽입할 node를 새로운 변수에 할당
        before_new = node.prev #원래 node의 이전 노드 변수로 정의
        before_new.next = new
        new.next = node
        return True

def insert_after(self, data, after_data):
    if self.head == None:
        self.head = Node(data)
        return True            
    else:
        node = self.head
        while node.data != after_data:
            node = node.next
            if node == None:
                return False
        new = Node(data)
        after_new = node.next
        new.next = after_new
        new.prev = node
        node.next = new
        if new.next == None:
            self.tail = new
        return True 

• before_new.next = new, new.next = node

• insert_before():

  

• insert_after():

  

• after_new.prev = new는 어디간걸까
• if new.next = None: self.tail = new는 왜 쓰는 걸까