Linked list

 

RAM(Random architecture Memory)

메모리에도 address가 있고, 각자의 위치에 데이터가 저장됨

각 주소에 접근할 때 걸리는 시간이 동일

메모리를 사용하는 특성이 다르다

 

LinkedList 구조

node : 마디, 교점

vertex: 정점, 꼭지점

연결과 연관되어 있는 개념

구조를 설명하기 위한 표현

 

node 안에 2개의 필드(변수)를 가지고 있다

data field: 저장되는 실제 값

link field:  다음 node가 무엇인가 저장 되어 있음

 

head : 첫번째 노드가 무엇인가를 의미하는 정보를 저장

 

첫번째 위치에 노드 추가

1. 노드를 생성

2. 새로 생성한 노드에 next값으로 현재 이 리스트의 첫번째 노드를 지정

3. 시작이 되는 node가 방금 생성한 node

 

데이터 중간에 추가 

 

array list와 차이 : 배열의 경우 중간에 추가/삭제할 경우 뒤에 있는 모든 엘리먼트들의 자리 이동 필요

=> 느림

linked list의 경우 추가/삭제 될 엘리먼트의 이전, 이후 노드의 참조 값(next)만 변경

=> 빠름 

 

특정한 위치 엘리먼트 삭제

 

 

Linked list : 노드의 크기를 무한대로 늘릴 수 있음. list 크기가 확정적이지 않음

Array list : 데이터 추가할 때 array의 크기를 넘어서면 에러 발생. 큰 배열 안에 3~4가지만 사용하면 메모리 낭비

---