파이썬으로 연결 리스트(linked list) 코드를 작성해보자

최근 다시 한 번 알고리즘, 자료구조를 공부하고 싶었다

솔직히 알고리즘까지는 아니더라도 자료구조라도 공부를 하고 싶었다

그래서 파이썬으로 코드를 작성하며 공부를 해보려고 한다

 

이번 편은 파이썬으로 해보는 자료구조 연결 리스트(linked list)이다

연결리스트는 어찌보면 배열과 비슷하지만 구조적으로 다르다

배열은 같은 성질끼리(요즘엔 언어에 따라서 다른 성질도 묶어도 되지만) 연속적으로 되어 있는 상태이다

연결 리스트(linked list)는 구조상으로 봤을 때 계속 링크를 따라서 이어지는 구조이다

이런식으로 말이다

하나의 노드에 데이터와 다음 노드를 가리키는 next point가 있다

이런 식으로 쭉 이어나가고 중간에 삽입, 삭제도 가능하도록 코드를 구성해보겠다

파이썬으로!

python data structure linked list

정말 간단하다

예전에 C언어로 구성했을 때는 정말 코드가 길었었는데 ㄷㄷ

Node 클래스를 하나 만들고 생성자에 data와 next를 둔다

그리고 node_A를 global로 두는데 node_A가 가장 첫 시작 포인트이기 때문이다

그리고 Node 객체를 생성하고 next 포인트에 각 노드를 넣어주면 된다

생각보다 엄청 간단하다

 

그럼 삽입, 삭제는 어떻게 될까?

삽입은 이렇다고 가정하자

입력되는 데이터가 어떤 데이터 포인트보다 작으면! 그 작아지는 시점에 데이터를 삽입한다

만약 A -> B -> D인데  C를 삽입하게 되면 C는 B보다는 크지만 D보다 작으니까 이때 삽입을 해주는 것이다

마찬가지로 먼저 Node class를 만든다

그리고 Node를 4개 만드는데 A, B, D, E를 만든다

 

이 부분은 삭제 부분이다

node_A를 global로 가지고 온 뒤 pre_node에 node_A를 넣어주고 next_node에 pre_node의 next 정보를 넣어준다.

그러면 맨 처음에는 next_node에는 B Node에 대한 정보가 담긴다

그리고 시작하자마자 만약 내가 삭제하려는 것이 NodeA에 대한 정보이면 node_A에 next_node 정보를 넣어주고(next node가 맨 처음이 되어야 하니까) pre_node를 삭제한다

만약 그게 아니면 삭제하려는 정보를 찾을 때까지 반복문을 통해 접근하면서 노드를 찾아내고 만약 정보가 있으면 삭제한다.

 

 

 

삽입도 비슷한 패턴이다.

마찬가지로 global로 node_A를 가져온 뒤 새로 삽입하려는 Node를 만들어준다.

그리고 현재 node_A 정보를 node_p, node_t에 넣어준다.

node_T는 node_P보다 +1 칸 앞서가는 애라고 생각하면 된다. 맨 처음은 둘다 node_A에 대한 정보를 갖고 있지만 node_T는 한 발짝 더 앞서 나간다.

만약 C를 넣으려고 하면 node_P는 node_B를 가르키고 있고 node_T는 node_D를 가리키고 있는 상태가 된다
(C를 넣으려고 할 때는 A -> B -> D -> E 니까)

그래서 C를 넣으려고 할 때 new_node.next에 node_T 정보를 주면 new_node가 D를 가리키게 되고

node_p.next = new_node를 통해 현재 B를 가리키고 있는 node_p의 next가 new_node를 가리키게 된다!

 

 

실제 보면 이렇게 나온다