연결리스트란?

노드에 분산하여 저장하고 링크로 연결 시키는 형태이다.
메모리에 비연속적으로 저장하기 때문에 크기제한이 없다.

연결리스트의 종류에는 단일,이중,원형 연결리스트가 있다.

연결리스트와 배열(array)의 차이

array

1, 접근이 쉽다.

• 메모리상에서 연속적인 데이터로 존재하기 때문에 index로 접근이 가능하다.

2, 삽입이 어렵다.

• 메모리에 먼저 연속적인 데이터로 만들기 위해 공간을 할당하기 때문에 삽입이 쉽지않다.

LinkedList

1, 직접구현해야한다.

• 여러언어에서 연결리스트를 기본으로 지원하지 않기 때문에 직접 만들어 써야한다.

2, 접근이 어렵다.

• 노드들은 서로 알지 못하고 내 다음 노드가 누구인지만 알기 때문에 탐색이 쉽지 않다.

3, 삽입이 쉽다.

• 마지막 노드에 링크를 새로 만들 노드에 연결 해주면 되기 때문에 삽입이 쉽다.

데이터 접근이 많을 경우 리스트 사용, 삽입 삭제가 많다면 linkedList사용

파이썬으로 구현

이런식으로 구현이 된다고 이해했다.
헤드는 그냥 저 객체를 가르키는 것이다.
next는 다음 노드를 가르키는 것인데 저 next값을 가져오면 객체를 가져오기 때문에 이렇게 생각했다.

#노드 생성 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val 		#데이터
        self.next = next 	#링크

#링크드 리스트 생성, self는 자기자신
class LinkedList: 
    def __init__(self):
        self.head = None	#포인터(위치)

    def append(self, val):
    	#head가 none을 가르키면 헤드에 Node추가하고 끝
        if not self.head: 
            self.head = ListNode(val, None)
            return
		
        #node변수에 self.head 할당
        node = self.head
        while node.next: #self.head.next가 없을때 까지 
            node = node.next #node에 node.next 할당
		
        #node.next는 None이니깐 ListNode 추가
        node.next = ListNode(val, None)