JAVA 자료구조 - 연결 리스트(LinkedList)개념정리

연결 리스트(Linked List) 개념정리

결국에 컴퓨터 프로그램이 활용하는 메모리 공간에는 용량 제한이 있다. 메모리는 위 바둑판과 같이 생긴 저장 공간으로 2차원 배열이라고 생각하면 쉽다.

실제로 그렇지는 않겠지만 엑셀처럼 행은 오름차순의 숫자의 주소를 가지고 열은 오름차순의 알파벳 주소를 가진다고 가정하자  그렇다면 array자체의 주소는 A1이고 각각 1 - B1, 2 - C1, 3 - D1, 4 - E1, 5 - F1, 6 - G1의 각각 주소를 가진다. 다른 말로 하면 각 간을 메모리도 다 별개의 주소가 있다.  

 

이렇게 이상적으로 배열을 메모리 위치가 서로 인접해 있다. 다음에 요소를 추가 할때는 A2에 추가 하는 것이 가장 이상 적일 것이다. 하지만  이미 A2에는 객체가 메모리를 차지하고 있을수 있다. 그래서 원래 array에 7번 째 요소가 A2에 들어가야 하는데 해당 칸을 사용하 수 없다. 그렇다면 그 다음에 비어있는 칸인 E2에 array의 7번째 요소를 추가해야 한다. 

 

컴퓨터는 메모리를 보고 데이터를 찾는다. array의 요소들 중 1, 2, 3, 4, 5, 6에 해당하는 요소들은 인접한 메모리 주소를 가지고 있기 때문에 자신의 다음 칸의 주소를 가져오면 된다. 하지만  요소 7를 찾고 싶은 경우 문제가 생긴다  6의 다음칸 메모리에는 object가 있다. 컴퓨터는 요소 6으로 배열이 끝난 것인지 아니면 object 가 차지하고 있는 메모리 주소가 끝나뒤에 이어지는 array의 다음 순번의 요소가 있는 지 알 수 없다. 

 

 

그래서 실제로는 배열의 요소을 하나 저장할때 다음 배열순번의 요소가 어느 위치에 저장이 되어 있는지에 대한 단서를 같이 가진다. 예를 들어 B1이라는 메모리 주소가 있으면, 값으로는 1을 가지고 있고, 이 요소의 다음 순번의 요소는 C1에 저장되어 있다와 같이 두개의 데이터를 가지고 있다. 그래야지 배열의 다음번에 오는 요소가 어느 메모리 주소에 위치하는지 알 수 있다. 배열의 마지막 값은 다음 값에 대해 null을 가진다. 

 

사슬처럼 서로 Chaning되어있다. 그래서 이것을 연결리스트 LinkedList라고 한다. 다음 요소에 대한 값이 하나만 존재해야 하는 것은 아니다. 2개의 값을 가질 수도 있다. 구현에 따라 자유롭게 하면 되는데 양방향 LinkedList도 있을 수 있고 한방향 LinkedList도 존재할 수 있다. 

 

그렇다면 A1이라는 연결리스트에 저장된 요소중에 ' 5 ' 라는 값을 찾고 싶다면 어떻게 해야 할까?  A1 → B1 → C1 → D1 → E1 → F1 과 같이 일일히 값을 조회하는 과정을 거친 이후에 F1이라는 메모리 주소에서 요소 5를 찾을 수 있다. 이럴 때 최악의 경우는 찾고 싶어하는 값이 가장 마지막에 있을 때이다. 

 

값을 찾는 것을 "조회" 라고 하는데 조회 action에 최악의 경우는 O(n)이라고 할 수 있다. 값을 삽입할 때도 A1 → B1 → C1 → D1 → E1 ... 와 같은 과정을 거친 뒤에 마지막에 E2에 다음 요소에 대한 메모리 주소가 없는 것을 발견하고 E2에 메모리 주소를 저장한다. 즉 삽입하는 것도 O(n)의 시간 복잡도를 가진다. 수정, 삭제도 최악의 경우는 마지막 요소를 수정, 삭제하는 것이기 때문에 수정과 삭제도 모두 O(n)이다. 따라서 연결리스트의 시간의 복잡도는 O(n)이다. 연결리스트의 단점은 다음 값은 알 수 있는 데 이전 값을 찾아 갈 수 없다는 것이다. 

 

연결 리스트Linked List는 컴퓨터 과학에서 배역과 함께 가장 기본이 되는 대표적인 선현 자료구조 중 하나로, 다양한 추상 자료형 Abstract Data Type 구현의 기반이 된다.

 

연결 리스트는 데이터 엘리먼트의 선형 집합이지만 데이터의 순서가 메모리에 물리적인 순서대로 저장되지 않는다. 이는 순서대로 저장되는 배열과의 가장 큰 차이점으로, 대신 동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며, 연결 구

조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다.

 

또한 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러가지 방법으로 다양하게 활둉이 가능하다. 실제로 연결 리스트는 컴퓨터의 물리 메모리상에 구조체 각가이 그림 8-1과 같이 서로 연결된 형태로 구성되어 있으며, 메모리 어딘가에 여기저기 흩뿌려져있다.

 

⭐연결 리스트는 배역과 달리 특정 인덱스에 접근하려면 전체를 순서대로 읽어야 하므로 상수시간에 접근할 수 없다. 즉 탐색에는 O(n)이 소요된다. 반면, 시작또는 끝 지점에 아이템을 추가하거나 삭제, 추출하는 작업은 O(1)에 가능하다.

 

자바에서 연결 리스트를 구현한 자료형은 자바 컬렉션 프레임워크에서 제공하는 LinkedList이며, 연결 리스트 특성상 다양한 인터페이스를 제공한다. 대표적으로 리스트가 될 수 있고 Queue 뿐만 아니라 Deque도 될 수 있다. 자바의 LinkedLists는 이중 연결 리스트(Doubly Linked List)이기 때문에 삽입과 추출이 양방향 모두 가능하다. 보통 자료형에서 연결리스트를 말할 때는 한쪽으로만 삽입과 추출이 가능한 단일 연결 리스트 Singly Linked List를 지칭하지만, 자바에서는 이미 이중으로 구현되어 있기 때문에 자바 자료형인 LinkedList를 언급할 때는 특별한 언급이 없는 한 이중 연결 리스트를 활용한다고 보면 된다. 

 

출처

비전공자의 전공자 따라잡기 - 자료구조(whith JavaScript) , 조현영

https://www.inflearn.com/course/%EB%B9%84%EC%A0%84%EA%B3%B5%EC%9E%90-%EC%A0%84%EA%B3%B5%EC%9E%90-%EB%94%B0%EB%9D%BC%EC%9E%A1%EA%B8%B0-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-javascript/dashboard

 

자바 알고리즘 인터뷰 with 코틀린 , 저 박상길

https://www.onlybook.co.kr/entry/java-algorithm-interview