[자료구조] Linked-List(연결리스트) 기초 (python)

---

 

 

연결리스트 개념

연결리스트는 인덱스가 존재하지 않고,

다음 데이터의 존재를 알려주는 다음 데이터의 주소값과 현재 데이터로 이루어져 있다.

그리고 데이터와 주소값, 두 요소로 이루어진 묶음 하나를 노드 라고 부른다.

그림으로 그리면 아래와 같다

연결리스트 노드 모양

연결리스트의 특징이자 장점이라면, 

 

필요한 부분에 필요한 데이터를 원할 때 마다 삽입, 삭제할 수 있다.

만약에 데이터 1과 떨어진 어떤 부분에 데이터 3을 넣고 싶으면, 

이전 데이터인 데이터 1에 데이터 3의 위치만(주소값) 기록한 후에 데이터 3을 넣는다.

만약에, 데이터 3이 마지막 데이터라면 주소값에 아무것도 들어가지 않을 것이다.

이를 통해 마지막 데이터라는 것을 안다.

 

--> 해당 노드에 주소값이 존재한다면 다음 노드가 있다는 것.

--> 해당 노드에 주소값이 없다면 해당 노드가 마지막 노드라는 것.

 

그럼 우리가 아는 그냥 리스트, 배열이랑은 뭐가 다른가?

배열의 모양

---

배열과 연결리스트 비교

 

	배열	연결리스트
논리적 순서 / 물리적 순서	순차적 / 순차적	순차적 / 순차적이지 않음
데이터 접근	인덱스만 알면 한번에 접근 가능	처음부터 연결 된 요소들을 통해 찾아야 함
데이터 관리	특정 데이터의 삽입, 삭제는 다른 데이터들을 옮기고 나서야 가능하다.	특정 노드의 주소값만 수정
요소 접근 기준	인덱스	주소값
시간복잡도(요소 접근)	O(1)	O(n)

 

그렇기 때문에 연결리스트와 배열을 이용해야 하는 상황은 각자 다르다.

 

배열은 인덱스만 안다면, 요소의 접근이 쉽고 빠르기 때문에

데이터를 많이 불러오는 작업을 한다면 배열을 이용하는 것이 좋을 것 같다.

연결리스트로 데이터를 불러오려면 매번 처음의 노드부터 서치를 시작해야 하기 때문이다.

 

데이터를 삽입, 삭제해야 하는 작업을 많이 한다면 양쪽 주소값만 수정하면 되는 연결리스트를 이용하는 것이 좋을 것 같다.

배열로 데이터를 삽입하거나 삭제한다면 해당 데이터를 삭제, 삽입하고 이후의 데이터들을 다 옮겨야 하기 때문에 상대적으로 비효율적이다.

---

연결리스트 구현하기

 

파이썬쟁이라서 파이썬으로 구현하겠다.

 

구현 전에, 파이썬의 객체지향 문법에 대해 알아야 하기 때문에,

아래의 링크에서 기초 문법을 배우고 오길 바란다.

위키독스

 

노드의 형태는 데이터와 주소값이 들어간다고 했다.

이 형태를 찍어 낼 클래스를 만들자.

 

# 노드를 찍어 낼 클래스
class Node:
	def __init__(self, data, address=None):
    	self.data = data
        self.address = address	# 노드 안에는 데이터와 주소값이 있다

# 노드는 first와 sec 각각 값이 들어가며, 주소값은 설정을 하지 않는다면 디폴트로 None이 삽입
firstNode = Node('first')
secNode = Node('sec')

# 첫째 노드의 주소값을 둘째 노드로 지정하면서 둘이 연결된다
firstNode.address = secNode

# 첫째 노드를 head(처음노드)로 지정해야 다른 노드들을 찾을 수 있다
head = firstNode

 

 

secNode 다음에 'third'를 삽입해보자.

마지막 노드가 무엇인지 찾고, 그 다음 순서에 추가하는 메소드를 만든다.

# 클래스와 초기화는 같고 add만 추가됨
class Node:
	def __init__(self, data, address = None):
    	self.data = data
    	self.next = next
    def addData(data):
    	node = head
        # 주소값이 없어질 때 까지 루프(마지막 노드 서치)
        while node.address:
        	node = node.address
        node.address = Node(data)

secNode = Node('second')
head = secNode
Node.add('third')

# 출력
node = head
while node.address:
	print(node.data)
    node = node.next
print(node.data)	# second \n third

---

개념은 이해를 했지만 구현은 스택, 큐와 다르게 꽤 골치아픈 것 같다.

한 변수에 다른 요소를 대체시키는 부분이 많아 보인다.