[JAVA] 배열과 연결리스트

자바의 해쉬에 대해서 정리해보자로 시작했는데

배열과 연결리스트에 대한 내용이 너무 많아서 다음편에 해쉬에 대해서 알아볼 것이다.

해쉬를 이야기 하기 전에 배열에 대해서 생각해보자

 

1. 배열

배열에서는 인덱스를 이용하여 빠르게 원하는 정보를 검색할 수 있다.

예를 들면

for(String str : list)

for(int i=0;i<N;i++)

등의 다양한 방법이 있을 수 있겠다.

하지만 배열에서 원하는 위치에 값을 삽입하거나 삭제를 할 시에는 문제가 발생한다.

 

1

2

3

4

5

6

7

 

해당 배열에서 4번째 값을 지우고 싶다면 다음과 같은 과정을 거쳐야한다.

1) 배열의 삭제

 

1. 4번째 공간의 4라는 값을 삭제한다.

1

2

3

5

6

7

 

2. 그 인덱스를 기준으로 오른쪽의 값들을 전부 한칸 왼쪽으로 이동시킨다.

1

2

3

5

6

7

7

 

사실 1번의 과정을 거치지 않고 그냥 덮어씌우는 방법을 사용해도 문제 없지만 일단 과정을 적어 두었다.

 

그렇다면 삽입의 과정은 어떠할까?

2) 배열의 삽입

 

1

2

3

4

5

6

7

 

이번에는 3번과 4번 사이에 10이라는 값을 넣고 싶다면 어떻게 해야할까?

 

1. 4부터 오른쪽 모든 값을 한칸씩 오른쪽으로 이동시킨다.

1

2

3

4

5

6

7

 

2. 원하는 위치에 값을 삽입해준다.

1

2

3

10

4

5

6

7

 

누군가는 이런 과정이 왜 많은 시간이 소요되는 거지? 라고 의문을 가질 수 있다. 현재는 7~8개의 값들만 배열에 저장되어 있기때문에 그렇게 생각할 수 있지만 만약, 크기가 10만인 배열에서 인덱스 2번째 위치에 새로운 값을 삽입하고 자 하면 어떻게 될까? 99,999개의 값을 한칸씩 오른쪽으로 이동해야하는 아주 비효율적인 상황이 발생한다.

 

이를 해결하기위해 생긴것이 연결리스트라는 개념이다.

연결리스트는 노드간 연결로 이루어진 리스트이다. 그림을 보자

 

1) 연결리스트

 

처음 HEAD가 있고 각 노드에는 값정보와 다음 가리키는 노드의 위치가 저장되어있다.

쉽게 풀어서 말하면 값이 리스트 형태로 저장되어 있고, 각 노드에 다음 노드의 위치가 개별적으로 저장되어있다.

 

1이라는 값 이외에 다음 노드의 정보인 2가 저장되어 있다.

그렇다면 삽입, 삭제시 기존 배열과 어떠한 차이가 있는지 보자

 

1. 삽입 

 

삽입시에는 각 노드의 Next node를 변경해주고  삽입된 노드안에 다음으로 접근할 Next node를 입력해줌으로써 삽입 과정이 끝나게 된다.

여러사람이 줄을 서고 서로서로 앞사람의 머리에 있는 숫자를 기억하고 있다 하였을때 중간에 새치기한 사람은 그 앞사람의 머리 숫자를 기억하고 새치기한 뒷사람은 새치기한 사람의 머리 숫자를 기억하는 방식이다.

어렵나요?

 

그럼 삭제는 어떠할까?

 

2. 삭제

 

삭제시에는 삭제된 노드의 앞노드의 Next node 값을 삭제된 노드의 Next node로 변경해주면 된다.

인덱스 2의 Next node는 3이다 이값을 인덱스 1의 Next node 값으로 적어주는 것이다.

 

 

 

이렇게 해서 배열과 연결리스트의 간단한 정리가 끝이났다.

다음은 해쉬를 다룰 것이다.