연결 리스트 구조

---

• 연결리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다.
  • 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조이다.

연결 리스트 장단점

---

• 장점
  • 데이터 공간을 미리 할당하지 않아도 된다.
    • 배열은 미리 데이터 공간을 할당해야한다.
• 단점
  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지는 않다.
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다.
  • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요하다.

연결 리스트 용어

---

• 노드(Node) : 데이터 저장 단위로 구성되어있다.(데이터 값, 포인터)
• 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드 주소를 가지고 있는 공간이다.

연결 리스트 구현

---

노드 구현

class Node:
    def __init__(self, data, next=None): # next의 기본값은 None
        self.data = data
        self.next = next

노드와 노드 연결하기(포인터 활용)

node1 = Node(1)
node2 = Node(2)
node1.next = node2 # 노드 연결
head = node1 # 노드 추적을 위한 맨 앞 노드의 주소를 head에 저장

연결 리스트에 맨 마지막에 데이터 추가하기

def add(data):
    node = head
    while node.next: # 다음 노드의 주소가 있으면 참, 없으면 거짓으로 마지막 노드를 구할 때 사용한다.
        node = node.next
    node.next = Node(data) # data를 가진 노드를 만들어 맨 뒤에 연결한다.

연결 리스트 데이터 검색하기

def findNode(data):
    count = 0 # data 값을 가진 노드가 몇 번째인지 확인하는 변수
    node = head
    while node:
        count += 1
        if node.data == data:
            print("{}번 째 노드에 있습니다. 값은 {}입니다." .format(count, node.data))
            return node
        else:
        	node = node.next

연결 리스트 사이에 데이터 추가하기

def addNodeInside(data, pre_node_data):
    node = head
    new_Node = Node(data)
    pre_node = findNode(pre_node_data)
        
    if pre_node == None:
        return print("해당 값을 가진 노드가 존재하지 않습니다.")
    elif pre_node.next == None:
        pre_node.next = new_Node
    else:
        new_Node.next = pre_node.next
        pre_node.next = new_Node

연결 리스트 전체 출력

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

연결 리스트 노드 삭제

1. head 노드 삭제
2. 맨 마지막 노드 삭제
3. 중간 노드 삭제

def deleteNode(data):
    if head == None:
        print("해당 값을 가진 노드가 존재하지 않습니다.")
    if head.data == data: # 1.헤드 노드 삭제
        temp = self.head
        head = head.next
        del temp # del : 객체 삭제 명령어
    else: # 2.마지막 노드 삭제, 3.중간 노드 삭제
        node = head
        while node.next:
            if node.next.data == data:
                temp = node.next
                node.next = node.next.next
                del temp
            else:
                node = node.next

테스트 해보기

node1 = Node(1)
head = node1

for index in range(2, 11): # 2부터 10까지의 값을 가진 노드를 생성한다.
    add(index)
   
printAll() # 출력 : 1 2 3 4 5 6 7 8 9 10
    
findNode(4) # 출력 : 4번 째 노드에 있습니다.

addNodeInside(12, 4)
printAll() # 출력 : 1 2 3 4 12 5 6 7 8 9 10

deleteNode(4)
printAll() # 출력 : 1 2 3 12 5 6 7 8 9 10

클래스에서 전체 구현

---

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 addLastNode(self, data):  # 연결리스트 맨 마지막에 노드를 추가하는 함수
        if self.head == None:
            self.head = Node(data)
        if self.head.next == None:
            self.head.next = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

    def addNodeInside(self, data, pre_node_data):  # 연결리스트 중간에 노드를 삽입하는 함수
        if self.head == None:
            self.head = Node(data)
            
        new_node = Node(data)
        pre_node = self.findNode(pre_node_data)

        if pre_node == None:
            return print("해당 값을 가진 노드가 존재하지 않습니다.")
        elif pre_node.next == None:
            pre_node.next = new_node
        else:
            new_node.next = pre_node.next
            pre_node.next = new_node

    def findNode(self, data):  # 연결리스트에서 찾는 값이 있는 노드가 몇번째인지 검색하는 함수
        if self.head == None:
            return None
        else:
            node = self.head
            while node:
                if node.data == data:
                    return node
                else:
                    node = node.next
            return None

    def deleteNode(self, data):  # 노드를 삭제하는 함수
        if self.head == None:
            print("리스트가 비어있습니다.")
        if self.head.data == data:  # 헤드 노드 삭제
            temp = self.head
            self.head = self.head.next
            del temp  # del : 객체 삭제 명령어
        else:  # 마지막 노드 삭제, 중간 노드 삭제
            node = self.head
            while node.next:
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                else:
                    node = node.next

    def printAll(self):  # 연결 리스트를 순회하며 출력하는 함수
        node = self.head
        while node:
            print(node.data)
            node = node.next