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

링크드 리스트( Linked List)

연결 리스트라고도 한다. 배열은 순차적으로 연결된 공간에 데이터를 나열하는 구조라한다면 링크드리스트는 떨어진 곳에 존재 하는 데이터를 연결해서 관리하는 자료 구조이다. 

Linked List의 기본 구현

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

Linked List의 단위 자료의 이름을 Node라고 한다. 이 Node가 다음 Node로 연결되는데 이 연결은 바로 next라는 변수로인해 가능해진다. data에는 저장하고자 하는 값이 들어가고 next에는 다음 Node의 주소가 저장된다.

---

Node와 Node의 연결

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

head = node1

node1과 node2가 생성 되었고 각각 1과 2로 값이 초기화 되었다. 즉 1과 2가 node1.data와 node2.data에 각각 저장되었다. 그리고 node1.next에 node2가 저장되어 next로 인해 다음 자료가 연결 되었다. 그리고 보통 Linked List의 시작 지점을 head라고 지칭한다.

---

Linked List로 데이터 추가 하기

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)
    
node1 = Node(1)       	// 1
node1.next = Node(2)	// 2

head = node1

// add 함수를 이용해 값 추가(Node 생성)
for i in range(3, 10):  // 3~9
    add(i)

// 변수  node에 시작 주소 head(node1) 저장
node = head

// next 가 존재 하면 해당 node의 data를 출력
while node.next:
    print(node.data)
    node = node.next
// next가 존재하지 않는 마지막 노드의 경우 data를 출력하고 종료
print(node.data)

/** 출력
1
2
3
4
5
6
7
8
9
**/

Linked List에 값을 추가하는 기능이 함수로 구현되었다. add 함수는 반복문 while 을 통해 Linked List 상에서 제일 마지막의 Node를 찾고 새로운 Node를 생성해서 이전 Node의 next에 저장한다. 

그리고 반복문 while을 통해 next가 존재하는 경우 data를 출력하고 next가 없는 마지막 Node의 경우 해당 Node의 data를 출력하고 본 코드는 종료된다.