LinkedList

• 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하여 하나의 전체적이 자료구조를 이룬다.
• 링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다.
• 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능하다.

노드

• 연결 리스트에서 하나의 원소에 필요한 데이터(주소값)를 갖고 있는 자료단위
• 구성 요소
  • 데이터 필드
    원소의 값을 저장하는 자료구조
    저장할 원소의 종류나 크기에 따라 구조를 정의하여 사용함
  • 링크 필드
    다음 노드의 주소를 저장하는 자료구조

헤드

리스트의 처음 노드를 가리키는 레퍼런스

단순 연결 리스트

• 연결 구조
  • 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가진다.
  • 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다.
  • 최종적으로 NULL을 가리키는 노드가 리스트의 가장 마지막 노드이다.

package test2;

public class Node {
	public int data;//데이터
	public Node next;//다음 노드의 주소값
	
	public Node(int data) {
		this.data=data;
		this.next=null;
	}
}
=================================================================
package test2;

public class singlyLinkedList {
	//연결리스트는 head만 저장하고 있으면 됨
	public Node head;
	
	public singlyLinkedList() {
		
	}
	
	//가장 마지막에 추가 : addToEnd
	//가장 처음에 추가 : addToStart
	//특정 값을 갖는 노드 다음에 추가 : addAfter
	//특정 위치에 있는 원소를 반환 : getNode
	//가장 마지막에 있는 노드 삭제 : deleteLast
	//가장 처음에 있는 노드 삭제 : deleteStart
	//특정 값을 갖는 노드 다음 노드 삭제 : deleteAfter
	//리스트를 순회해서 출력 : printList
	
	public void addToEnd(int data) {
		//새로운 노드 생성
		Node n=new Node(data);

		//리스트가 비어있는지 여부 먼저 체크
		if (head==null) {//리스트가 비어있다면
			head=n;
		}
		else {
			//가장 마지막 노드 찾기
			Node curr=head;//임시변수 curr에다가 가장 첫번째 노드의 주소값을 저장해 놓고 시작
			while (curr.next!=null) {//그 다음 노드가 있다면
				curr=curr.next;//그 다음 노드로 이동				
			}
			//while문이 끝났다면?
			//curr.next==null
			//curr-> 가장 마지막 노드를 가리키고 있는 상태
			
			//가장 마지막 노드의 다음에 새로운 노드를 추가
			curr.next=n;
		}
	}
	
	public void printList() {
		Node curr=head;
		System.out.print("LinkedList[head: ");
		
		while (curr!=null) {
			System.out.print(curr.data+"->");
			curr=curr.next;
		}
		System.out.println("]");
	}
	
	public void addToStart(int data) {
		//새로운 노드 만들기
		Node n=new Node(data);
		//현재 첫번째 노드는 head를 통해서만 접근 가능
		//현재 첫번째 노드는 두번째 노드가 되어야 함
		//새로운 노드.next<=현재 첫번째 노드의 주소값(head)
		n.next=head;
		
		//head가 새로운 노드 가리키도록 하기
		//head=<새로운 노드의 주소값
		head=n;
	}
	
	//target이라는 값을 갖는 노드의 주소값을 반환
	public Node getNode(int target) {
		Node curr=head;
		while (curr!=null) {
			if (curr.data==target) {
				return curr;
			}
			curr=curr.next;
		}
		return null;//노드를 찾지 못했다면 null반환
	}
	//target이라는 값을 갖는 노드를 찾아서 그 다음에 data라는 값을 갖는 노드 삽입
	public void addAfter(int target, int data) {
		Node targetNode=getNode(target);
		if (targetNode!=null) {//노드를 찾았다면
			Node n=new Node(data);
			n.next=targetNode.next;
			targetNode.next=n;
		}
	}
}
================================================================
package test2;

public class test {
	public static void main(String[] args) {
		singlyLinkedList list=new singlyLinkedList();
		list.addToEnd(13);
		list.addToEnd(88);
		list.addToEnd(39);
		list.addToStart(1);
		list.addToStart(2);
		list.addAfter(13, 44);
		list.addAfter(44, 55);
		list.printList();
	}
}
//
LinkedList[head: 2->1->13->44->55->88->39->]

LinkedList 사용법

package test1;

import java.util.LinkedList;

public class test1 {
	public static void main(String[] args) {
		LinkedList<Integer> list=new LinkedList<>();
		
		list.add(1); // add:가장 뒤에 추가
		list.addLast(2); //addLast:가장 뒤에 추가
		list.addFirst(3); //addFirst:가장 앞에 추가
		list.add(2, 4); //특정 인덱스에 추가->2인덱스에 4추가
		
		list.remove(2);//특정 인덱스 원소 제거
		list.remove();//가장 앞에 있는 원소 제거
		list.removeFirst();//가장 앞에 있는 원소 제거
		list.removeLast();//가장 뒤에 있는 원소 제거
		
		list.offer(4);//가장 뒤에 추가
		list.push(5);//가장 앞에 추가
		list.pop();//가장 앞에 있는 것 튀어나옴
		list.add(6);
		list.add(7);
		list.poll();//가장 앞에 있는 것이 튀어나옴
		
		System.out.println(list.size());
		System.out.println(list.isEmpty());
		System.out.println(list);
		
	}
}
2
false
[6, 7]

값 추가 : .add()

값 변경 : set(a,b)->a번 인덱스 값을 b로 변경

첫번째 데이터 삭제 : removeFirst(), remove()

마지막 데이터 삭제 : removeLast()

인덱스 순번의 데이터 삭제 : remove(a)

모든 데이터들을 삭제 : .clear()

크기 : .size()

출력 : get()

값 검색(boolean) : .contains("hello")->있다면 true, 없으면 false

값 검색(index값 리턴) : indexOf("hello")->있다면 인덱스 값 나오고 없다면 -1출력