[자료구조] 링크드 리스트 (Linked List)

• 링크드 리스트를 내 손으로 구현할 줄 알아야한다...!^^

링크드 리스트 구조

• 링크드 리스트 = 연결 리스트
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조, 단점은 연결된 공간이 준비돼있어야한다는 점. 데이터 저장공간이 떨어지는 순간 배열의 역할을 할 수 없음
• 이러한 배열의 단점을 커버하기 위해서 사용하는 것이 링크드 리스트
• 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
• 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원

링크드 리스트 관련 용어

• 노드: 데이터 저장 단위 (데이터값 + 포인터)
• 포인터: 각 노드 안에서 다음/이전의 노드와의 연결정보를 가지고 있는 공간
• 맨 앞에 있는 노드의 주소만 알 수 있다면 전체 데이터에 접근이 가능함
• 마지막 데이터의 경우, 포인터의 값이 null임(그 다음에 연결되는 노드가 없기 때문에)

---

코드 구현

• 파이썬의 객체지향 문법 이해 필요 / 보통 파이썬에서 링크드 리스트 구현시 파이썬 클래스를 활용하기 때문.

Node 구현

#Node에는 두가지 정보가 들어가기 때문에 이걸 표현하기 위해 클래스 사용

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

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

Node와 Node 연결 (포인터 활용)

node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1

데이터 추가하기

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)

링크드 리스트 데이터 출력하기(검색)

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

---

장단점

장점

• 미리 데이터 공간을 할당하지 않아도 됨

단점

• 연결을 위한 별도의 데이터 공간이 필요함(포인터를 저장할 공간) → 저장공간 효율이 높지 않음
• 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
• 중간 데이터를 삭제할 경우, 앞뒤 데이터의 연결을 재구성해야하는 부가적인 작업이 필요

---

링크드 리스트의 복잡한 기능

중간에 데이터 삽입

1. 삽입하고자 하는 포인터를 찾음
2. 기존 node의 포인터가 새로운 node를 가리키게 하고
3. 새로운 node의 포인터가 node.next를 가리키게 해야함

node3 = Node(1.5)

search = True
node = head
while node.next:
	if node.data == 1:
		search = False
	else:
		node = node.next

node_next = node.next
node.next = node3
node3.next = node_next

중간에 데이터 삭제

1. head 노드를 삭제하는 경우, head의 값을 임시 변수에 옮겨두고 head를 head.next값으로 변경 후 임시 변수 삭제
2. 중간 노드 혹은 마지막 노드 삭제하는 경우, 삭제하려는 노드의 전에 연결된 노드를 찾고 삭제하려는 노드를 임시변수에 옮겨둔 후 전에 연결된 노드의 next를 삭제하려는 노드의 next와 연결. 그리고 임시변수 삭제

def delete(self, data): #이 데이터를 가진 노드를 삭제해라
        if self.head == '': #노드가 아예 없는 경우 (방어 코드)
            print ("해당 값을 가진 노드가 없습니다.")
            return
        
        if self.head.data == data: #1.head 노드를 삭제하는 경우
            temp = self.head #객체를 삭제하기 전, 옮겨두기 -> 만약 self.head 객체를 삭제하면 이 코드가 실행이 안되기 때문에
            self.head = self.head.next #두번째 노드를 head에 넣는 과정
            del temp #객체를 삭제
        else:
            node = self.head #일단 넣어놓고(그 다음꺼부터 확인하기 위해)
            while node.next: 
                if node.next.data == data: #2.중간 노드 삭제하는 경우, 3.마지막 노드 삭제 모두 커버 가능
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    return
                else:
                    node = node.next #지우려고 하는 데이터를 찾을 때까지 서칭~

---

파이썬 객체지향 프로그래밍으로 링크드 리스트 구현

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 == '': #방어코드의 일환으로, 만약에 head값이 없다면 node가 존재하지 않는다고 생각하고 데이터를 추가한다.
            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

---

더블 링크드 리스트

• 이중 연결 리스트
• 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능

코드 구현

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 #node가 한개 일때는 head, tail 모두 똑같기 때문에 

    def insert(self, data):
        if self.head == None:#아직 node가 안만들어진 상태
            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 node랑 연결
            new.prev = node #새로 추가한 노드의 전 주소를 기존 node와 연결
            self.tail = new #해당 리스트의 tail을 new node와 연결
            #여기서 new node의 next를 none으로 굳이 말해주지 않는 이유는 Node class에서 next의 default 값이 none으로 설정돼있기 때문

    def desc(self): #리스트 전체를 프린트해주는 코드
        node = self.head
        while node:
            print (node.data)
            node = node.next

데이터가 특정 숫자인 노드 앞에 새로운 데이터를 추가하는 함수

• tail에서부터 이동하며 특정 숫자인 노드를 찾는 방식으로 함수 구현하기

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
    while node:
        if node.data == data:
            return node
        else:
            node = node.prev
    return False

def insert_before(self, data, before_data): #before_data: 새로운 데이터를 앞에 넣을 노드의 데이터
    if self.head == None:
        self.head = Node(data)
        return True
    else:
        node = self.tail
        while node.data != before_data: #찾는 데이터를 찾을 경우 while문 break
            node = node.prev
            if node == None:
                return False
        new = Node(data)
        before_new = node.prev
        before_new.next = new
        new.prev = before_new
        new.next = node                
        node.prev = new
        return True