Linked List

1. Linked List?

노드라는 구조체가 연결되는 방식으로 데이터를 저장하는 자료구조

 

1-1. 구성?

• value : 데이터 값
• NEXT :  다음 데이터의 주소 값
• Node : 두개를 합친 데이터 자체

메모리 상에서는 비연속적으로 저장되어 있지만 각각의 node가 다음 node의 주소값을 가지고 있기 때문에 논리적으로는 연속적으로 저장되어있음 이것을 물리적 비연속적, 논리적 연속적 이라고 한다

Array List에서는 연속적으로 값을 저장하기 위해 순차적으로 데이터를 저장하였지만 Linked List는 연속성을 유지하지 않아도 되기 때문에 메모리 사용이 조금 더 자유롭다

1-2. 노드의 구현

class Node :
    def __init__(self, value = 0, next = None):
        self.value = value
        self.next = next
        
first = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)

1-2-1. 구성

class Node :
    def __init__(self, value): # init이라는 노드 생성
    	# 노드의 벨류와 next 값을 초기화 해줌
        self.value = value
        self.next = None

위와같이 생성된 상태

first = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)

노드를 네개 생성해본다

현재는 노드가 네개 만들어졌지만 아직 연결은 안된 상태이다

first.next = second
second.next = third
third.next = fourth

연결을 시켜준다

1-2. Class 선언해서 만들기

class LinkedList(object):
    def __init__(self):
        # Linked List의 첫번째 요소
        # 처음엔 비어있으니 None으로 초기화
        self.head = None

class LinkedList(object):
    def __init__(self):
    	self.head = None
    def append(self, value):
    	pass
                
                
                
                
 ll = LinkedList()
 ll.append(1)
 ll.append(2)
 ll.append(3)
 ll.append(4)

append메서드로 연결을 시켜주게되면

이렇게 Next가 연결되게 된다

1-3-1. append 구현해보기

class LinkedList(object):
    def __init__(self):
    	self.head = None # 1. 현재 head 값은 주소값만 있는상태(연결 안되어있음)
    def append(self, value):
    	# 2. 위에서 만들어둔 Node 클래스를 호출하여 node를 하나 만듬
    	new_node = Node(value)
        if self.head is None: # 노드의 Next가 None이라면
            self.head = new_node # 3. 첫번째 노드를 head로 지정
        else: # 아니라면(new_node 변수로 인해서 next 값이 들어있다면)
            ptr = self.head
            while(ptr.next): # 4. next의 값이 없을때 까지 반복(없다면 마지막 노드임)
                ptr = ptr.next    
            ptr.next = self.current = new_node # 5. next 값 지정

1-3-2. doubly-Linked-List

우리는 1 -> 2 -> 3 -> 4 이렇게 연결했지만 이걸 확장해서 양방향으로 연결되게 구현할 수 있다.

class Node(object):
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None # 노드가 생성될때 이전 주소를 가리키게 함


class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None # 이전 주소 연결

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node