02/08(2) - 리스트 (순차리스트 ,연결리스트)

리스트 : 순서를 가진 데이터의 집합 

- 순차 리스트 : 배열을 기반으로 한 리스트 

- 연결 리스트 : 메모리의 동적 할당 ( 즉 , 객체 ) 를 기반으로 한 리스트

 

[ 순차리스트 - ArrayList ] 

삽입 : 중간에 값을 삽입, 기존의 있던 그 이후의 값들은 뒤로 한칸씩 밀려나게 됨 

삭제 : 중간의 값을 삭제, 기존으 있던 그 이후의 값들은 앞으로 한칸씩 오게 됨 

--> 연속적인 메모리 관리를 해야하기 때문에 삽입이나 삭제시 메모리의 이동이 필요 

 , 이러한 연산들이 많아지면 오버헤드가 발생하고 데이터 관리 소요시간이 증가하게 됨 

--> 배열의 크기가 정해져 있기 때문에, 너무 크게 만들면 메모리 낭비 / 너무 작게 만들면 배열 복사 작업 많아짐 

오쪼라고 ,,,  잘만들어라고 ,,, 

---

[ 연결리스트 - LinkedList ]

데이터 즉, 자료의 논리적인 순서와 물리적인 순서가 다름 

- 논리적인 순서는 서로 연결되 있더라도, 객체를 기반으로 관리하기 떄문에 , 물리적인 순서는 따로 없음 

각자 독립적이고 개별적인 원소로 위치하고 있는데, 멀리 떨어져있더라도 각각의 원소를 연결하여서 하나의 자료구조 ! 

--> 메모리가 동적으로 할당 되어있고 객체로서 관리하기 때문에, 크기 또한 동적으로 관리가 가능 

즉, 메모리의 효율적인 사용이 가능하다 

- 노드 ( Node ) : 데이터 필드 ( 데이터 , 값 ) + 링크 필드 ( 다음 노드의 참조값 ) 

- 헤드 ( Head ) : 가장 첫 노드를 가리키고 있음, 헤드가 가장 첫 노드를 가리키므로써, 뒤의 모든 노드들이 일자로 연결 

 

1) 단순 연결 리스트 : 가장 기본적인 연결리스트의 구조 , 선형리스트 

 : 각 노드가 하나의 데이터 필드와, 하나의 링크 필드로 이루어져 있음 

-> 문제점 : 중간의 노드를 빼기 위해선, 그 노드의 바로 직전 값과 직후 값을 연결시켜주어야 하는데, 이전 노드에 대한 정보는 가지고 있지 않기 때문에, 그에 대한 정보를 얻기 위해선 헤드 부터 다시 읽으면서 직전 노드를 찾아내야함 ! 

 

2) 이중 연결 리스트 : 두개의 링크필드를 가지고 있어, 직전 값과 직후 값 두개를 참조 할 수 있음 

: 단순 연결리스트의 문제점을 해결 할 수 있음 - 이전노드의 정보도 가지고 있기 떄문에 ,처음부터 하나하나 다시 탐색할 필요가 없어짐 

-> 문제점 : 하지만 두개의 참조를 관리해야하기 때문에 단순 연결리스트 보다는 관리의 어려움이 있음 

 

3) 원형 연결 리스트 : 마지막에서 처음으로 연결이 가능 

: 기본 단순 연결리스트는 중간값을 참조하게 되면, 한방향으로만 흐르기 때문에, 그 이후값만 읽어드릴 수 있었다. 

하지만 원형리스트로 마지막값과 처음값을 연결하게 되면, 그 이전값도 읽을 수 가 있다 .