(2) Linked list

■ Linked list 구조

1) 정의 :

연속된 메모리 위치에 저장되지 않는 선형 데이터 구조

> 포인터를 사용하여 연결 된다

> 용량 / 전기적 이유로 HDD / SSD에서 읽어와서 memory에 올려서 메모리 포인터의 값을 프로그래밍 언어가 사용

> 다음과 같은 구조를 가짐

 

2) 사용 이유 :

(1) array의 단점

- 배열 크기가 미리고정되어있어 유동적으로 데이터 사이즈에 따른 자료구조 변경이 어려움

- 새로운 요소를 삽입하는 것에 비용이 많이 소모( 공간을 만들고, 기존 요소 전부 이동시켜야 함 )

   > 요즘 언어들은 array에 대한 push pop

 

(2) Linked list의 장점

1. 동적 크기
2. 삽입/삭제 용이

(3) Linked list의 단점

1. 임의 access허용 불가능, 노드 앞단부터 순차적으로 찾고자 하는 대상을 검색하야 함
2. 포인터를 위한 여분의 공간이 각 노드에 필요

---

■ Python 객체지향을 이용한 linked list 예

> Python은  list 데이터 타입에서 이미 제공하나, class로도 같은 방식 구현 가능

1) 단순 연결

// 객체지향 node 선언
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
        
// 노드와 노드 연결
node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1

2) 데이터 추가

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

// 데이터 추가하는 함수
def add(data):
    node = head
    while node.next:
        node = node.next
    node.next = Node(data) 

node1 = Node(1)
head = node1
// node1을 head로 한 상태에서 None이면 다음 데이터 추가
for index in range(2, 10):
    add(index)
    
// 데이터 출력(검색)
node = head
while node.next:
    print(node.data)
    node = node.next
print (node.data)

>>>
1
2
3
4
5
6
7
8
9

3) 객체지향으로 링크드 리스트

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에 담아서 객체를 삭제했음
            if self.head.next: # 다음 node가 존재한다면
                self.head = self.head.next # 만약 self.head 객체를 삭제하면, 이 코드가 실행이 안되기 때문!
            else:
                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

> 테스트 코드

# 테스트
print(f'생성 후 바로 삭제 테스트')
node_mgmt = NodeMgmt(0)
node_mgmt.delete(0)
node_mgmt.desc() # 출력 없음, 테스트 성공!
print(f'')

print(f'1~9 까지 데이터 추가 테스트')
for data in range(1, 10):
    node_mgmt.add(data)
print(f'데이터 출력 테스트')
node_mgmt.desc()
print(f'')

print(f'4번 데이터 탐색 테스트')
node = node_mgmt.search_node(4)
print (node.data)
print(f'없는 데이터 "a" 탐색 테스트')
node_2 = node_mgmt.search_node('a')
print(str(node_2))

>>>
생성 후 바로 삭제 테스트

1~9 까지 데이터 추가 테스트
데이터 출력 테스트
1
2
3
4
5
6
7
8
9

4번 데이터 탐색 테스트
4
없는 데이터 "a" 탐색 테스트
None

 

■ 추가 기능을 가진 구조

> 양방향 search 도 있음

---

참조 :

opentutorials.org/module/1335/8821

Linked list - Data Structure (자료구조)

gyoogle.dev/blog/computer-science/data-structure/Linked%20List.html

Linked List | 👨🏻‍💻 Tech Interview