선형자료구조 연결리스트(Linked List)
연결리스트(Linked List)
데이터를 링크로 연결해서 관리하는 자료구조
자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음
연결리스트의 장점
데이터 공간을 미리 할당할 필요x -> 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이
연결리스트의 단점
연결구조를 위한 별도 데이터 공간 필요
연결 정보를 찾는 시간이 필요(접근 속도가 상대적으로 느림)
데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요
연결리스트 기본구조
✔️노드(Node): 데이터 저장 단위로, 값과 포인터(다음 노드나 이전 노드의 연결 정보)로 구성
연결리스트 기본연산
✔️데이터 추가:
어디에 데이터를 추가할지에 따라 연결 작업이 다르다!
-가장 앞에 데이터를 추가할 때:
1. 추가할 데이터를 담을 노드 생성
2. 링크 연결 작업
3. head 이전 작업
-가장 끝에 데이터를 추가할 때:
1. 추가할 데이터를 담을 노드 생성
2. head로부터 끝 노드까지 순회
3. 링크 연결 작업
-중간에 데이터를 추가할 때:
1. 추가할 데이터를 담을 노드 생성
2. head로부터 데이터 추가 위치 직전 노드까지 순회
3. 링크 연결 작업
✔️데이터 삭제:
데이터 추가와 마찬가지로 삭제할 데이터의 위치에 따라 연결 작업이 다르다.
-가장 앞의 데이터 삭제 시:
1. 삭제 대상 노드 지정(delete node)
2. head 이전 작업
3. delete node 삭제
-가장 끝의 데이터 삭제 시:
1. head로 부터 가장 끝까지 순회
2.끝 노드 삭제
3. 삭제 이전 노드의 링크 처리
-중간 데이터 삭제 시:
1. head로부터 삭제 대상 노드까지 순회, 그리고 삭제 노드 지정
2. 삭제 대상 이전/이후 노드의 링크 연결 작업
3. delete node 삭제
LinkedList 코드 구현하기
class Node{
int data;
Node next;
Node(){}
Node(int data, Node next){
this.data = data;
this.next = next;
}
}
class Linkedlist{
Node head;
Linkedlist(){}
Linkedlist(Node node){
this.head = node;
}
//연결리스트 비어있는지 확인
public boolean isEmpty(){
if(this.head == null){
return true;
}return false;
}
//연결리스트의 맨 뒤에 데이터 추가
public void addData(int data){
if(this.head == null){
this.head = new Node(data, null); //new node 생성
}else{
Node cur = this.head; // 순회할 노드 cur, 끝꺼지 순회
while (cur.next != null){ //가장 마지막까지!
cur = cur.next;
}
cur.next = new Node(data, null); //새 노드 만들고 데이터 넣기
}
}
//연결리스트의 맨 뒤의 데이터 삭제
public void removeData(){
if(this.isEmpty()){
System.out.println("list is empty!");
return;
}
Node cur = this.head;
Node prev = cur; //cur를 쫓아다닐 node prev 만들기
while (cur.next != null){
prev = cur;
cur = cur.next;
}
if(cur == this.head){
this.head = null;
}else{
prev.next = null; //prev.next를 null 처리하면 맨 뒤 데이터는 삭제
}
}
//데이터 찾기
public void findData(int data){
if(this.isEmpty()){
System.out.println("list is empty!");
return;
}
Node cur = this.head;
while(cur != null){
if (cur.data == data){ //찾고자하는 data인지 확인..!
System.out.println("Data exist!");
return;
}
cur = cur.next; //찾을때까지 cur을 이동시킨다.
}
System.out.println("Data not found!");
}
//모든 데이터 출력
public void showData(){
if(this.isEmpty()){
System.out.println("list is empty!");
return;
}
Node cur = this.head;
while(cur != null){
System.out.println(cur.data+ " "); //data를 공백으로 구분해 차례로 출력한다.
cur = cur.next;
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
//Test code
Linkedlist myList = new Linkedlist(new Node(1, null));
myList.showData(); //1
myList.addData(2);
myList.addData(3);
myList.addData(4);
myList.addData(5);
myList.showData(); //1 2 3 4 5
myList.findData(3); //Data exist!
myList.findData(100); //Data not found!
myList.removeData();
myList.removeData();
myList.removeData();
myList.showData(); //1 2
myList.removeData();
myList.removeData();
myList.removeData(); //list is empty
}
}
양방향 연결리스트, 원형 연결리스트는 각각 prev node를, prev node와 head, tail 추가해 구현해준다.
처음엔 노드의 개념에서 포인터의 개념이 너무나 헷갈렸는데,
코드를 여러 번 구현해가며 연결리스트의 링크가 어떻게 되는지를 이해할 수 있었다.
아직 원형리스트의 구현이 쉽지 않기 때문에, 여러 번 코드를 구현해가며 다시 이해해야겠다.
또한 연결리스트의 구현, 연결리스트의 활용이 어디에 될 지 감이 안오기 때문에,
아직 풀어보지 않은 예제를 풀며 연결리스트의 활용을 알아갈 것이다.