[자료구조] 2023_0828 연결리스트

박희현·2023년 8월 28일

MSG study 자료구조

MSG STUDY

목록 보기

2/7

8/28 자료구조 스터디

[02] 연결 리스트 (Linked List)

연결리스트의 목적과 이론
연결리스트의 장점과 단점
연결 리스트와 배열의 공통점과 차이점
연결 리스트의 구조
연결 리스트의 연산
연결 리스트의 구성요소
코드를 작성해서 활용문제 만들어보기
- ex) 해당 코드의 출력결과는?

[ 연결리스트의 목적과 이론 ]

연결리스트란?
연결리스트는 노드의 연속이라 할 수 있다
연결리스트는 배열과 달리 추가, 삭제가 용이하기 때문에 추가, 삭제를 많이 하게 될 경우 사용하게 된다

[ 연결리스트의 장점과 단점 ]

장점 : 데이터를 자유롭게 삭제, 삽입할 수 있다
단점 : 한 요소에 바로 접근이 불가하고 연결 된 링크를 따라가야만 한다

[ 연결 리스트와 배열의 공통점과 차이점 ]

연결리스트	배열
`연결 리스트`는 크기를 미리 정하지 않고 동적으로 필요한 만큼 메모리를 할당받아서 만든다, 즉 리스트 길이가 가변적이다	`배열`은 미리 크기를 정하고 데이터를 넣기 때문에 overflow error 또는 공간낭비가 발생할 수 있다
하나의 노드들이 불특정 공간에 있어 pointer를 사용하여 연결시켜주어야 한다 따라서 어떤 값을 찾으려면 연결 된 링크들을 거쳐가야만 하기 때문에 선형시간이 더 걸리게 된다 ->불연속 공간	배열은 모든 원소들이 이어진 메모리 공간이므로 배열의 인덱스를 통한 효율적인 탐색이 가능하다 ->연속 공간
시간복잡도 -> O(n)	시간복잡도 -> O(1)
동적할당	정적할당
데이터 추가, 삭제 시 이동한다	데이터 축, 삭제 시 용이하다

[ 연결 리스트의 구조 ]

연결 리스트가 데이터를 저장하는 법은 노드가 데이터와 포인터를 가지고 한 줄로 이어진 방식이다.. 이때 포인터는 다음 노드의 주소값을 가지고 있다 여기서 노드란 것은 데이터를 갖고 있는 하나의 요소이다. 또한 노드는 데이터와 포인터를 함께 지니고 있다
하나의 연결 리스트가 완성 되었을 때 맨 앞의 노드를 Head노드, 맨 뒤의 노드를 tail노드라고 한다

[ 연결 리스트의 연산 ]

연결 리스트의 연산엔 기본적으로 삽입과 삭제가 있다
삽입은 삽입할 위치를 지정하여 삽입 위치 앞의 노드의 pointer의 주소값을 삽입할 노드의 주소값으로 지정해준다. 그 후 삽입할 노드의 pointer의 주소값은 삽입노드 뒤에 있는 노드의 주소값으로 지정해주고 삽입하면 된다
삭제는 삭제할 노드를 삭제한 후 삭제노드 앞에 있던 노드의 pointer의 주소값을 삭제노드 뒤에 있던 노드의 주소값으로 지정해준다

[ 연결 리스트의 구성요소 ]

연결리스트에는 head, 노드, body, data, pointer, tail이 있다. 하나의 연결 리스트가 완성 되었을 때 맨 앞의 노드를 Head노드, 맨 뒤의 노드를 tail노드라고 한다. 중간의 노드들을 body라고 하고 노드 안에는 data와 pointer가 있다. data는 값을 가지고 pointer는 다음 노드의 주소값을 가진다.

[ 코드를 작성해서 활용문제 만들어보기 ]

package Linkedlist;

import java.util.ArrayList;

class Linkedlist{
	public static void main(String []args) {
		ArrayList<String> student = new ArrayList<String>();
		student.add("최수빈");
		student.add("토끼");
		student.add("아깽이");
		student.add("빈수최");
		//1
		System.out.println(student.size());
		
		//2
		System.out.println(student.get(2));
		
		//3
		for(int i=0; i<student.size(); i++) {
			System.out.print(student.get(i)+" ");
		}
		System.out.println();
		student.remove(1);
		
		//4
		for(int i=0; i<student.size(); i++) {
			System.out.print(student.get(i)+" ");
		}
		System.out.println();
		student.clear();
		
		//5
		System.out.print(student);
		
	}
}