[자료구조] 연결 리스트 (Linked list)

0. 개요

	순차 리스트	연결 리스트
장점	i 번째 원소의 값 접근이 빠름 연속된 값 읽기가 빠름	원소의 삽입 / 삭제가 빠름
단점	원소의 삽입 / 삭제가 느림	i 번째 원소의 값 접근이 느림 연속된 값 읽기가 느림

 

✔️ 메모리

컴퓨터에는 3가지 중요한 부품

1. CPU
2. 메모리(memory) : RAM
3. 스토리지(storage) : HDD/SSD

 

메모리 : 속도 빠르다. 용량이 작다. 전기를 끄면 데이터가 사라진다.

스토리지 : 속도 느리다. 용량이 크다. 전기를 꺼도 데이터가 남아있다.

 

따라서 데이터는 기본적으로 스토리지에 저장되고 프로그램을 실행할 땐 프로그램과 데이터는 메모리로 옮겨져 CPU는 메모리에 로드된 데이터로 작업을 한다.

 

🚩 자료구조를 공부하는 이유: 메모리의 효율적인 사용

 

 

1. 구조

출처: 위키백과

node (vertex) : 데이터 저장 단위 (Data field, Link field)로 구성

pointer : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

Head : 첫 번째 노드가 무엇인지에 대해 저장

 

 

2. 초기화 (init)

다음 노드를 가리키는 포인터를 null로 설정한다.

 

• 파이썬

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

 

3. 데이터 삽입

✔️ 가장 앞에 삽입

• 슈도코드

// 노드를 생성한다.
Vertex temp = new Vertex(input)
// 첫번 째 노드를 정한다.
temp.next = head
// 시작이 되는 노드가 새로 생성된 노드라는 것을 정한다.
head = temp

 

✔️ 중간에 삽입

 

출처: 위키백과

• 슈도코드

Vertex temp1 = head
//현재 k의 값은 2
while (--k!=0)
  temp1 = temp1.next
Vertex temp2 = temp1.next
Vertex newVertex = new Vertex(input)
temp1.next = newVertex
newVertex.next = temp2

 

4. 데이터 삭제

• 슈도코드

Vertex cur = head
//현재 k의 값은 2
while (--k!=0)
  cur = cur.next
Vertex tobedeleted = cur.next
cur.next = cur.next.next
delete tobedeleted

 

 

순차 리스트는 삽입/삭제 시 노드의 자리 이동이 필요했다. 하지만 연결 리스트는 삽입/삭제 시 해당 노드 전, 후의 참조값(next)만 변경하면 되기 때문에 속도가 빠르다.

 

5. 구현

 

• Java

https://opentutorials.org/module/1335/8857#entirecode

 

---

📌 Reference

• [생활코딩] Linked list
• [잔재미코딩] 링크드 리스트