자료구조(연결 리스트)

링크드 리스트(Linked List)

링크드 리스트는 연결 리스트라고한다. 배열은 미리 특정한 공간을 사전에 할당해야 하는 확장성이 떨어지는 단점을 보완하기 위하여 나온 것이 링크드 리스트(연결 리스트)이다. 즉 배열의 단점을 극복한 자료구조이다.

배열 vs 링크드 리스트

배열은 데이터만 담고 있다. 하지만 링크드 리스트에는 데이터와 다음 데이터를 가리 키는 주소를 가지고 있는데 (데이터 + 다음 데이터의 주소)를 묶어서 노드 라고 한다.

연결 리스트 기본 주고와 용어:

노드: 데이터 저장 단위(데이터 + 포인터(다음 데이터의 주소))
포인터: 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

링크드 리스트의 데이터 추가

class Node:   # Node class 생성
    def __init__(self, data, next = None): #Node가 만들어질 때 해당하는 값 넣기
        self.data = data 
        self.next = next
def add(data): #Node 뒤에 값 연결하기
    node = head #node에 head 연결해주기  
    while node.next:  #node의 다음 주소값이 있으면 반복문 실행
        node = node.next #현재 노드의 값을 다음 노드의 값으로 옮겨주기
    node.next = Node(data) #반복문을 벗어나서 실행 => 다음 노드의 주소값 즉 포인터가 없다 = 연결리스트
                           #의 마지막 부분이다. 현재 비어있는 포인터에 다음 노드의 데이터 값 넣어주기 

node1 = Node(1)  #node1 이라는 변수에 Node클래스 생성
head = node1 # head는 node1이라고 설정
for index in range(1,10): #1부터9까지 add 실행
    add(index)
node = head # 앞에서 설정한 head(연결리스트의 첫번째 노드)를 node 변수에 넣기
while node.next: #노드의 포인터가 없을 때 까지(연결리스트의 마지막 노드까지)
    print(node.data) #노드의 데이터 출력
    node = node.next #다음 노드로 이동
print(node.data) #마지막 노드의 데이터 출력

링크드 리스트의 장단점

장점:
1. 저장공간을 사전에 확보하지 않아도 된다.
단점:
1. 연결된 주소(포인터를 저장하는 공간)를 별로로 저장해야 함으로 저장공간 효율이 높지 않다.
2. 정로를 찾는데 시간이 필요하기 때문에 접근 속도가 느리다.(배열에서는 인덱스로 바로 접근 가능)
3. 중간에 노드를 추가하거나 삭제할 때 앞뒤 노드의 포인터를 수정해줘야하는 추가 작업이 필요하다.

링크드 리스트 중간에 데이터 넣기

node_add = Node(3.5) #위에서 만든 코드에서 추가로 node_add라는 변수에 Node(3.5)를 생성한다.
node = head #다시 node 변수를 리스트의 처음 노드로 바꿔준다.
search = True
while search: #search 값이 False가 될 때까지 실행
    if node.data == 3: #만약에 node.data가 3이면
        search = False # search 값을 False로 바꿔준다.
    else: #아니면
        node=node.next # node를 다음 node로 바꿔준다.
tmp = node.next #현재 노드안에는 3이라는 데이터를 가지고 있다. 다음 노드의 주소를 tmp 에 담고
node.next = node_add #node.next에 새로 들어갈 노드의 값을 넣어준다.
node_add.next = tmp #새로 들어갈 노드의 next 값에는 기존의 node의 다음번에 나오는 node의 주소를 담아놨던 tmp의 값을 넣어준다.
node = head  #다시출력
while node.next:
    print(node.data)
    node=node.next
print(node.data) # 1 2 3 3.5 4 5 6 7 8 9

링크드 리스트 구현 최종

class Node:
    def __init__(self,data,next=None):
        self.data = data
        self.next = next
class LinkedList: #LinkedList 클래스안에서 Node클래스를 호출해서 사용하게 만듬 
    def __init__(self,data):
        self.head = Node(data)
    def add(self,data): 
        if self.head=='': #만약에라도 혹시 값이 없을 때 오류를 방지하기 위해서 head 가 비어있다면
            self.head = Node(data) #첫번째 노드에 값을 넣고 그것을 head로 하것다.
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)
    def display(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: #삭제하려고 하는 데이터가 첫번재 노드인 경우
            tmp = self.head
            self.head = self.head.next
            del tmp #삭제하려는 주소를 메모리에서 삭제
        else: #삭제하려고 하는 데이터가 첫번째 노드가 아닌경우
            node = self.head
            while node.next:
                if node.next.data == data: #이미 첫번재 노드가 아니기 때문에 node.next 부터 검사
                    tmp = node.next
                    node.next = node.next.next
                    del tmp
                    pass
                else:
                    node = node.next        

더블 링크드 리스트(이중 연결리스트)

이중 연결리스트가 나온 배경:
일반적인 연결리스트는 무조건 앞에서 부터 다음 노드로 순서로 검사를 진행을 한다. 하지만 만약에 내가 원하는 데이터가 백만개의 노드를 가진 연결리스트의 뒤에서 3번째 노드라고 한다면 일반적인 연결리스트에서는 99만 9997번의 검사를 해야하는 비효율적인 방법을 사용해야한다. 이러한 문제를 해결하기 위해서 나온것이 이중 연결리스트이다. 이중 연결리스트는 노드에 앞의 노드의 주소와 뒤의 노드의 주소를 가지고 있기 때문에 뒤에서부터 검사하여 3번만에 원하는 노드를 찾을수 있다.

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

class doubleLink:
    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
        else:
            node = self.head
            while node.next :
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new
    
    def search_head(self,data):
        if self.head == None:
            return False
        else:
            node = self.head
            while node.next:
                if node.data == data:
                    return print('find the data: ', data) 
                else:
                    node = node.next
            return False
    
    def search_tail(self,data):
        if self.head == None:
            return False
        else:
            node = self.tail
            while node.prev:
                if node.data == data:
                    return print('find the data: ', data)
                    
                else:
                    node = node.prev
            return False
    
    def insert_before(self, data, before_data):
        if self.search_head(before_data) == False:
            return print('값을 찾을 수 없습니다.')
        else:
            node = self.head
            while node.data != before_data:
                node = node.next
            new = Node(data)
            new.prev = node.prev
            node.prev.next = new
            new.next = node
            node.prev = new
            
            return print('성공')
    
    def display(self):
        node =self.head
        while node:
            print(node.data)
            node = node.next
            
test = doubleLink(0) # test 변수에 더블링크드리스트 생성 첫번째 값은 0
for data in range(1,5): # test에 1,4까지 값 넣기 test의 head는 0 tail은 4 
    test.insert(data) # test = 0,1,2,3,4
test.search_tail(3) # find the data: 3
test.insert_before(3,2) # test안에 2라는 값을 먼저 찾고 그 앞에 3이라는 데이터 삽입
test.display() # 결과 0,1,3,2,3,4