자료구조 - 연결 리스트

 

리스트 : 순서가 있는 데이터를 늘어놓은 자료구조

 

- 선형 리스트 (배열을 이용)

- 연결 리스트 (단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트)

 

---

연결 리스트 쓰는 이유 ? 

 

배열을 이용한 선형리스트을 이용할 경우  :  

선형 리스트 = ["홍길동", "김삿갓", "설까치"] 

1번 자리에 인원 추가 하기 위해

 

 

3번 데이터 공간 만들기

 

 

1,2번 데이터 옮기기

 

 

"김철수" 추가

 

 

 

 

단점 : 크기가 먼저 정해져 있어서, 데이터 양에 따라 메모리 낭비 or 데이터 추가가 어렵다.

장점 : 구현하기 간단하다. 데이터 탐색 속도(접근속도) 빠르다.    

          = 데이터 순서O , 데이터 삭제/삽입 이 없다면 선형리스트가 좋다.

 

---

연결 리스트의 기본 구조 

A ~ F 까지 데이터가 순서대로 나열, 각 데이터가 화살표로 연결됨 

 

 

각각의 원소 (element)

= 노드(node)

 

 

노드가 갖고 있는것 =

데이터 + 뒤쪽 노드를 가리키는 포인터 

 

 

 

 

 

노드 구현 코드

class Node:

    def __init__(self, data, next=None):   # 마지막에는 None이므로 미리 만들어줌
        self.data = data    # 데이터
        self.next = next    # 뒤쪽 노드 가르키는 포인터

 

class Linked_list:
    # 첫번째 헤드값을 받음
    def __init__(self, data):
        self.head = Node(data)
        # self.head.data => 어떤 특정 값
        # self.head.next => 주소값 node (data,next)
    
    # 링크드 리스트 값 추가
    def add(self, data):
        if self.head == "":   
            self.head = Node(data)
            
        else:  # 새로 들어온게 비어있는 값이 아니면
            node = self.head  
            # 연결리스트의 연결 부분
            while node.next:   # None이 나올 때 까지 반복문을 돌린다. 
                node = node.next
            node.next = Node(data, next = None)
    
    def delete(self, data):
        if self.head == "":
            print("빈노드")
        
        # 헤드의 값을 지울 떄
        if self.head.data == data:
            self.head = self.head.next
        else:
            node = self.head
            # 모든 노드를 순회하며 값을 찾음
            while node.next:
                if node.next.data:
                    node.next = node.next.next
                    return
                else:
                    node = node.next
        
    
    def __repr__(self):
        node = self.head
        temp = []
        while node:
            temp.append(node.data)
            node = node.next
        return f"{temp}"

---

연결 리스트의 삽입 / 삭제

삽입

 

head : 머리 노드에 대한 참조

 

 

 

새로운 데이터를 삽입 할 때,

포인터가 참조 하도록 추가해준다.

 

 

 

 

삭제

 

삭제할 데이터가 참조했던 포인터를 삭제 하고 이어준다.

 

 

 

 

 

 

 

장점 : 메모리를 효율적으로 사용한다. 데이터 재구성이 용이하다. 길이 제한이 없다.

단점 : 특정 위치 데이터를 찾을 때 느리다. 메모리 추가적으로 사용 (노드주소 저장)

---

이중 연결 리스트 ( Doubly linked list )

연결리스트의 단점 

뒤쪽 노드를 찾기 쉬우나, 앞쪽 노드를 찾기는 어렵다.

 

뒤쪽 노드에 대한 포인터 + "앞쪽 노드에 대한 포인터" 가 추가 된다.

 

장점 : 앞쪽 노드에 대한 접근이 가능하다.

단점 : 메모리 사용이 늘어난다.

 

 

---

원형 연결 리스트 ( Circular linked list ) 

연결 리스트의 꼬리 노드가 다시 머리 노드로 포인터를 이용하여 연결 되어 있다.

 

장점 : 순환되는 데이터 구조를 표현할 때 용이하다.

단점 : 구현이 어렵다.

 

 

---

원형 이중 연결 리스트 ( Circular Doubly linked list )

원형 리스트 + 이중 연결 리스트 의 결합

 

 

---

 

 

 

 

 

 

 

 

 

출처

Do it 자료구조와 함께 배우는 알고리즘 입문 - 파이썬편

https://2dubbing.tistory.com/53 [비실이의 개발 성장기]

www.youtube.com/watch?v=eTwYE-ercNM