[Data Structure] Linked List

LinkedList란

연결 리스트는 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.

데이터들을 갖고 있는 하나의 요소가 노드이다. 노드 속에 다음 노드를 가리키고 있다.

특히, 제일 앞에 있는 노드는 헤드(head), 제일 끝 노드는 테일(tail)이라고 부른다.

 

head와 tail은 데이터 필드는 있지만 쓰지 않을 것이다. 단지 구현의 용이함을 위해서 사용하였는데,
만약 head와 tail의 데이터 필드를 쓰게 되면  추가, 삭제시 3가지를 고려해야한다.

1) 추가, 삭제할 노드가 맨 앞 노드인가
2) 추가, 삭제할 노드가 맨 뒤 노드인가
3) 추가, 삭제할 노드가 중간 노드인가

하지만 head와 tail의 data를 쓰지 않는다면 3)번 조건만 고려하면 된다.

이처럼 아무 데이터가 없는 노드를 더미노드라고 한다.

 

LinkedList 특징

 

1. 노드의 삽입, 삭제 작업이 용이하다.

2. 기억공간이 연속적으로 놓여 있지 않아도 저장이 가능하다.

3. 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억공간 이용 효율이 좋지 않다.

4. 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.

5. 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

6. 희소 행렬 을 링크드 리스트로 표현하면 기억장소가 절약된다.

7. 트리를 표현할 때 가장 적합한 자료 구조이다.

 

Linked List 사용하는 이유

링크드리스트의 가장 큰 장점은 리스트의 길이가 가변적이다.

배열의 단점을 링크드리스트가 커버 할 수 있다.( 배열의 경우 길이가 고정 )

 

 

Single Linked List

---

제너릭을 활용하여 T 타입을 받는 Node라는 클래스가 있다고 가정해보자.

T 타입인 data가 있고, 그 다음 노드를 가르키는 next라는 변수가 있다.

 

public class Node<T> {
	
	public T data;
	public Node<T> next; //나 자신과 동일한 타입이어야한다.
	
	
	public Node(T item) {
		this.data = item;
		this.next = null;
	}
	
}

 

다음 Node가 존재하지 않는다면 null이기 때문에 초기 값을 null로 설정해줬다.

 

public static void main(String[] args) {
		// 만약 문자열을 저장 받고 싶다면 이러한 형태가 될것이다.(제네릭 타입으로 아무 타입으로 사용할 수 있도록 설계했기 때문)
		MyLinkedList<String> list = new MyLinkedList<String>();

		list.add(0, "MONDAY");
		list.add(1, "SUNDAY"); // M -> S
		list.add(0, "FRIDAY"); // F -> M -> S
		list.add(2, "TUESDAY"); // F -> M -> T -> S 이런 순서로 저장됨

		String str = list.get(2); // TUESDAY 리턴
		list.remove(2); // TUESDAY 삭제 F -> M -> S 순서로 바뀜

		int pos = list.indexOf("FRIDAY"); // 0을 리턴 FRIDAY 값이 첫번째 값이므로
	}

 

MyLinkedList라는 클래스의 객체를 생성하였다.(현재의 클래스)

add메소드를 통하여 해당 값을 넣어줄 수 있는데 해당 인덱스에 값이 존재할 경우 그 데이터는 다음 인덱스로 밀리고 새로운 값이 추가되는것을 볼 수 있다. ( 삭제 또한 마찬가지 / 값이 사라지면 한칸씩 땡겨짐. )

 

public class MyLinkedList<T> {

	// 단반향 링크드리스트(싱글)
	public Node<T> head; // 첫번째 노드의 값
	public int size; // 현재 Node의 크기를 저장할 변수

	// 기본 생성자
	public MyLinkedList() {
		this.head = null;
		this.size = 0;
	}
}

 

초기 Node의 경우 값이 없기 때문에 head가 가르키는 방향이 null이 될것이며 size 또한 0

 

Node 맨 앞쪽으로 값이 추가될 경우

 

public void addFirst(T item) {
		// 새로 추가될 데이터를 노드의 맨앞쪽으로 넣어줄 메소드
		// 1. 새로운 값을 저장하는 노드 생성
		Node<T> node = new Node<T>(item);

		// 2. 새로 생선된 node에 현재 head가 가르키는 다음 주소값을 저장해둔다.
		node.next = head;
		head = node;

		// 값이 추가됐으므로 size 증가
		this.size++;

	}

 

T 타입의 데이터가 들어와 node에 값이 추가 되게 된다.

 

이때, 해당 node의 다음 node는 head 즉 null 값을 가지게 된다.

( 하나의 Node가 생성되었고 그 다음 노드는 존재하지 않으므로 )

그리고 다시 head가 가르키는 방향은 새로 만들어진 node를 가르키게 된다.

 

 

Node 중간에 값이 추가될 경우(특정 인덱스 뒤쪽으로)

public void addAfter(Node<T> before, T item) {
		// 새로운 노드 생성 -> 데이터 저장
		Node<T> temp = new Node<T>(item);

		temp.next = before.next;
		before.next = temp;

		this.size++;
	}

 

특정 Node의 위치 뒤에 새로운 데이터가 들어왔을 경우이다.

 

먼저, 들어온 데이터를 가지고 새로운 Node를 생성하였다.

생성된 Node가 가르키는 방향은 기존에 있던 Node가 가르키는 방향이 될것이고,

기존 Node가 가르키는 방향을 다시 새로운 Node로 초기화 시켜 기존 Node 다음에 새로운 Node가 위치할 수 있도록

 

 

일반적으로 값이 추가될 경우

 

// index번째에 T타입의 데이터를 추가한다.
public void add(int index, T item) {
		
		if(index < 0 || index > size) {
			return;
		}
		if(index == 0) {
			addFirst(item);
		} else {
			Node<T> q = getNode(index -1);
			addAfter(q,item);
		}
	}

 

먼저 유효성 검사

index 가 존재하지 않거나, 가지고 있는 Node의 크기보다 큰 인덱스 번호가 왔을 경우에 따라 반환할 값을 설정해준다.

** 현재에서는 void 타입이라 return값에 아무것도 안준것 !! 수정할 예정

 

1. Node가 처음 만들어지는 경우

위에서 사용했던 addFirst()메소드가 실행되어 Node가 만들어지게 된다.

 

2. Node가 존재할 경우

현재의 index번호에 새로운 Node를 생성한다.

해당 인덱스가 가지고 있는 주소값을 반환 getNode() 메소드

 

// 해당 인덱스의 주소를 반환
public Node<T> getNode(int index) {

		if (index < 0 || index >= size) {
			return null;
		}

		Node<T> temp = head; // 연결리스트 첫번째 노드를 저장

		for (int i = 0; i < index; i++) {
			temp = temp.next;
		}
		return temp;
	}

 

특정 인덱스 번호를 가지고 해당하는 Node의 주소값을 반환 받는 getNode() 메소드이다.

 

유효검사를 통하여 잘못된 값이 들어올 경우 null을 반환하고 있다.

또한 초기 Node의 값을 head값 즉, null로 설정하여 초기 값을 기억해둔다.

 

반복문을 통하여 생성된 Node가 다음 방향을 가르킬 수 있도록 초기화 시킨다.

 

해당 인덱스의 데이터를 반환 get() 메소드

 

// 해당 인덱스의 데이터를 반환
public T get(int index) {
		//유효성 체크를 위해 조건문만 살리고
		if(index < 0 || index >= size) { return null; }
		 
		 /** Node<T> temp = head; //연결리스트 첫번째 노드를 저장
		 * 
		 * for(int i=0;i<index;i++) { temp = temp.next; }
		 */
         
         
		// 코드가 중복되므로 이러한 형태로도 사용가능
		return getNode(index).data;
	}

 

코드의 중간에 보면 getNode() 메소드와 중복이 되게된다.

 

따라서 return 값으로 getNode메소드를 사용하여 데이터만 반환하게 해주어 사용할 수 있다.

 

하지만, 저렇게 값만 return했을 경우 잘못된 값 즉, 존재하지않는 값이 들어왔을 경우 에러가 발생하게 된다.

따라서 유효성 검사를 통하여 null을 반환함으로써 에러를 막을 수 있다.

 

특정 데이터를 가지고 있는 노드의 위치를 반환 indexOf() 메소드

 

public int indexOf(T item) {

		Node<T> temp = head;

		int index = 0;

		while (temp != null) {
			if (temp.data.equals(item)) {
				return index;
			} else {
				temp = temp.next;
				index++;
			}

		}
		return -1; // 데이터가 존재하지 않는다면 -1 리턴
	}

 

데이터가 들어있는 Node의 인덱스 값을 반환

 

 

첫번째 Node를 삭제할 경우

 

public T removeFirst() {

		if (head == null) {
			return null;
		} else {
			T temp = head.data; // 삭제될 데이터를 리턴 시킬 것이므로( 임시 변수에 저장 -> 예제이기 때문에 리턴값을 주지만 보통의 remove는 리턴값이 void 일
								// 경우가 많다.)
			this.head = head.next; // head가 가르키는 다음 next값을 현재 head에 새로 저장(첫번째 노드가 지워지면 다음 노드를 가르키므로)

			this.size--; // 값이 지워졌으므로 size --

			return temp;
		}
	}

 

처음 삭제할 head == null 이 경우, 즉 노드가 존재하지 않을 경우 null 반환.

Node가 존재한다면 head가 가르키는 next 즉, null 로 저장한다.

 

** T 타입의 데이터 변수는 삭제할 Node의 값을 반환하기 위하여 생성된 변수.

 

 

 특정 노드 다음의 노드를 삭제할 경우

 

public T removeAfter(Node<T> before) {

		if (before.next == null) {
			return null;
		} else {
			T temp = before.next.data;
			before.next = before.next.next; // 삭제된 노드의 다음 노드를 가르켜야 하므로 next.next

			this.size--;

			return temp;
		}
	}

 

before이라는 Node의 다음 Node를 삭제할 것이다.

 

1. before의 다음 Node가 존재 하지 않을 경우 null을 반환.

2. before의 다음 Node가 존재할 경우

 

before가 가르키는 방향을 next.next인데 이는 현재 before 노드가 가르키는 Node의 next값을 가르키게 된다.

 

** T타입의 변수는 삭제할 Node의 데이터를 저장하기 위해 선언된 변수.

 

2가지의 remove 메소드 

1. 인덱스 번호를 가지고 노드를 지울 경우

 

public T remove(int index) {
		
		if(index < 0 || index >= size) {
			return null;
		}
		
		if(index == 0) {
			return removeFirst();
		}
		
		Node<T> temp = getNode(index - 1);
		return removeAfter(temp);
		
	}

 

 

2. 특정 데이터를 가지고 있는 Node를 지울 경우

 

public T remove(T item) {
		Node<T> p = head , q = null;
		
		while(p != null && !p.data.equals(item)) {
			q = p; // q는 p의 값을 저장 즉, 삭제 할 노드
			p = p.next; // p는 다음 노드
		}
		
		if(p == null) {
			return null;
		} 
		
		if(q == null) {
			return removeFirst();
		} else {
			return removeAfter(q);
		}
		
	}

 

학습을 위하여 라이브러리를 사용하지 않고, 직접 메소드를 만들어 사용하였는데 

 

라이브러리를 사용할 경우 ArrayList의 사용법과 같다.

 

LinkedList list = new LinkedList();//타입 미설정 Object로 선언된다.
LinkedList<Student> members = new LinkedList<Student>();//타입설정 Student객체만 사용가능
LinkedList<Integer> num = new LinkedList<Integer>();//타입설정 int타입만 사용가능
LinkedList<Integer> num2 = new LinkedList<>();//new에서 타입 파라미터 생략가능
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));//생성시 값추가

 

객체를 생성하여 사용하면 된다.