单链表：
概念：
1、由于线性表的顺序存储在插入与删除时需要移动大量元素，适用于不经常改变元素的情况，那么当我们需要经常操作元素时该怎么办，这就有了接下来的线性表的链式存储结构
2、单链表在内存的存储位置不一定是一段连续的位置，它可以存放在内存中任何地方
3、单链表中除了用于存放数据的数据域外，还有存放指针的指针域，指针域的作用是指向链表的下一个节点（因为链表的元素在内存中的存放时任意位置的，所以需要指向下一个节点）
4、单链表第一个节点存储的位置叫做头指针，整个单链表的存取都是从头指针开始，单链表的最后一个节点是指针指向空（NULL）
#
单链表的操作：
package com.alibaba.test03;
import org.junit.jupiter.api.Test;
/**
* 1. 单链表的具体实现及操作
* @author wydream
*
*/
public class SingLeLinkedList {
private int size;//链表节点的个数
private Node head;//头结点
public SingLeLinkedList() {
size=0;
head=null;
}
//链表中的每个节点类
private class Node{
private Object data;//每个节点的数据
private Node next;//每个节点指向下一个节点的连接
public Node(Object data){
this.data=data;
}
}
//在表头添加元素
public Object addHead(Object obj) {
Node newHead=new Node(obj);
if(size==0) {
head=newHead;
}else {
newHead.next=head;
head=newHead;
}
size++;
return obj;
}
//在链表头删除元素
public Object deleteHead() {
Object obj=head.data;
head=head.next;
size--;
return obj;
}
//查找指定元素，找到了返回元素Node，找不到返回Null
public Node find(Object obj) {
Node current=head;
int tempSize=size;
while(tempSize>0) {
if(obj.equals(current.data)) {
return current;
}else {
current=current.next;
}
tempSize--;
}
return null;
}
//删除指定的元素，删除成功则返回true
public boolean delete(Object value) {
if(size==0) {
return false;
}
Node current=head;
Node previous=head;
while(current.data!=value) {
if(current.next==null) {
return false;
}else {
previous=current;
current=current.next;
}
}
//如果删除的是第一个节点
if(current==head) {
head=current.next;
size--;
}else {//删除的不是第一个节点
previous.next=current.next;
size--;
}
return true;
}
//判断链表是否为空
public boolean isEmpty() {
return size==0;
}
//显示节点信息
public void display() {
if(size>0) {
Node node=head;
int tempSize=size;
if(tempSize==1) {//当前链表只有一个节点
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0) {
if(node.equals(head)) {
System.out.print("["+node.data+"->");
}else if(node.next==null){
System.out.print(node.data+"]");
}else {
System.out.print(node.data+"->");
}
node=node.next;
tempSize--;
}
System.out.println();
}else {//如果链表一个节点都没有，直接打印
System.out.print("[]");
}
}
@Test
public void test() {
SingLeLinkedList s=new SingLeLinkedList();
s.addHead("1");
s.addHead("2");
s.addHead("3");
s.addHead("4");
s.deleteHead();
s.display();
}
}
有序链表：
概念：
- 前面的链表实现插入数据都是无序的，在有些应用中需要链表中的数据有序，这称为有序链表。
- 在有序链表中，数据是按照关键值有序排列的。一般在大多数需要使用有序数组的场合也可以使用有序链表。有序链表优于有序数组的地方是插入的速度（因为元素不需要移动），另外链表可以扩展到全部有效的使用内存，而数组只能局限于一个固定的大小中。
有序链表的实现：
/**
*
* @author wydream
*
*/
public class OrderLinkedList {
private Node head;
private class Node{
private int data;
private Node next;
public Node(int data) {
this.data=data;
}
}
public OrderLinkedList() {
head=null;
}
//插入节点，并按从小到大的顺序排列
public void insert(int value) {
Node node=new Node(value);
Node pre=null;
Node current=head;
while(current!=null&&value>current.data) {
pre=current;
current=current.next;
}
if(pre==null) {
head=node;
head.next=current;
}else {
pre.next=node;
node.next=current;
}
}
//删除头节点
public void deleteHead() {
head=head.next;
}
public void display() {
Node current=head;
while(current!=null) {
System.out.println(current.data+" ");
current=current.next;
}
System.out.println("");
}
}
双向链表：
概念：
我们知道单向链表只能从一个方向遍历，那么双向链表它可以从两个方向遍历。
双向链表的实现：
import org.junit.jupiter.api.Test;
/**
* 双向链表的实现
* @author wydream
*
*/
public class TwoWayLinkedList {
private Node head;//链表头
private Node tail;//链表尾
private int size;//链表长度
private class Node{
private Object data;
private Node next;
private Node prev;
public Node(Object obj){
this.data=obj;
}
}
public TwoWayLinkedList(){
size=0;
head=null;
tail=null;
}
//在表头添加新节点
public void addHead(Object obj) {
Node node=new Node(obj);
//如果链表长度为零，则添加的这个元素就是头节点和尾节点
if(size==0) {
head=node;
tail=node;
}else {
head.prev=node;
node.next=head;
head=node;
}
size++;
}
//在链表尾添加新节点
public void addEnd(Object obj) {
Node newNode=new Node(obj);
if(size==0) {
head=newNode;
tail=newNode;
}else {
tail.next=newNode;
newNode.prev=tail;
tail=newNode;
}
size++;
}
//删除链表头
public Node deleteHead() {
Node temp=head;
if(size!=0) {
head=head.next;
head.prev=null;
size--;
}
return temp;
}
//删除链表尾
public void deleteEnd() {
Node end=tail;
if(size!=0) {
tail=tail.prev;
tail.next=null;
size--;
}
}
//获取链表节点个数
public int getLength() {
return size;
}
//判断链表是否为空
public boolean isEmpty() {
if(size>0) {
return true;
}
return false;
}
//显示节点信息
public void display() {
if(size>0) {
Node node=head;
int tempSize=size;
if(tempSize==1) {
System.out.println("["+node.data+"]");
return;
}
while(tempSize>0) {
if(node.equals(head)) {
System.out.print("["+node.data+"->");
}else if(node.equals(tail)) {
System.out.print(node.data+"]");
}else {
System.out.print(node.data+"->");
}
node=node.next;
tempSize--;
}
System.out.println();
}else {
System.out.println("[]");
}
}
@Test
public void test() {
TwoWayLinkedList tl=new TwoWayLinkedList();
tl.addEnd("1");
tl.addEnd("2");
tl.addEnd("3");
tl.addEnd("4");
tl.deleteHead();
tl.deleteEnd();
tl.display();
}
}