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

자료의 길이를 미리 정해야 한다는 단점을 극복하기 위해 링크드 리스트가 나옴

 

링크드 리스트는 미리 크기를 정하지 않고 그때그때 추가할 수 있다.

 

 

링크드 리스트는

 

  - 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성
  - 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

데이터 저장공간	다음 데이터 저장 주소 (포인터)
노드 (Node)

 

실제 링크드 리스트가 저장되는 방식(일자 형식이 아니다)

 

첫번째 Node만 알고 있다면 나머지 데이터에 접근 가능. 위와 같은 구조이기 때문에 데이터를 무한정 저장할 수 있다.

 

 

링크드 리스트를 구현하려면 객체지향 문법을 알고 있어야 한다.

파이썬에서 객체지향 문법을 모른다면. (10~12)

• 참고: https://www.fun-coding.org/PL&OOP1-3.html

 

 

Node와 Node연결하기

node1 = Node(1)
node2 = Node(2)
node1.next = node2 #  <<< node1의 포인터에 node2주소 저장

head = node1 #  <<<< 첫번째 node의 주소값은 별도의 변수로 저장해 둔다.

---

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) # << next가 None라면 여기가 실행 (마지막 노드)

자~ 보자

 

head = Node(1)이다

 

for문의 index=2일때

add(data)가 실행

Node(1)은 아직 next 값이 없다. 그래서 while문을 건너 뛰고 Node(1).next = Node(2) => 위치를 저장.

Node(1) 데이터	Node(2) 포인터
data	next

다음 index=3일때 

이번에 실행된 Node(1)은 next값이 생겼다.  

다음 node에 Node(2)포인터 값을 주니 Node(2).next를 검사하는데 없어 Next값이 그래서 while문을 나와 아랫줄 실행.

 

node1 = Node(1)
head = node1
for index in range(2, 10):
    add(index)

 

결국 인덱스가 9까지 가면 출력결과는 다음과 같다.

node = head
while node.next: #node.next에 값이 있다면 실행
    print(node.data)
    node = node.next
print (node.data)

1

2

3

4

5

6

7

8

9