链表是一种根据元素节点逻辑关系排列起来的一种数据结构。利用链表可以保存多个数据，这一点类似于数组的概念，但是数组本身有一个缺点—— 数组的长度固定，不可改变，在长度固定的情况下首选的肯定是数组，但是在现实的开发之中往往要保存的内容长度是不确定的，那么此时就可以利用链表这样的结构来代替数组的使用。
链表是一种最为简单的数据结构，它的主要目的是依靠引用关系来实现多个数据的保存。
下面是定义一个简单的类用来保存节点关系，并将所有节点链接起来。
例子1:
//每一个链表实际上就是由多个节点组成的
class Node {
private String data; //用于保存数据
private Node next; //用于保存下一个节点
public Node(String data){ //每一个Node类对象都必须保存有数据
this.data = data ;
}
public void setNext(Node next){
this.next = next ;
}
public Node getNext(){
return this.next ;
}
public String getData(){
return this.data ;
}
}
public class LinkedList {
public static void main(String[] args) {
//第一步：准备数据
Node root = new Node("火车头") ;
Node n1 = new Node("车厢A") ;
Node n2 = new Node("车厢B") ;
// 链接节点
root.setNext(n1);
n1.setNext(n2);
//第二步：取出所有数据
Node currentNode = root ; //从当前根节点开始读取
while( currentNode != null){
System.out.println(currentNode.getData()) ;
//将下一个节点设置为当前节点s
currentNode = currentNode.getNext() ;
}
}
}
运行：
火车头
车厢A
车厢B
例子2:
在进行链表操作的时候，首先需要的是一个根节点（第一个节点即为根节点），之后每一个节点的引用都保存在上一节点的next属性之中，而在进行输出的时候也应该按照节点的先后顺序，一个一个取得每一个节点所包装的数据。
public class LinkedList {
public static void main(String[] args) {
Link link = new Link() ;
link.add("hello"); //增加节点
link.add("world");
link.add("wwww");
link.print(); //打印数据
}
}
//每一个链表实际上就是由多个节点组成的
class Node {
private String data; // 用于保存数据
private Node next; // 用于保存下一个节点
public Node(String data) { // 每一个Node类对象都必须保存有响应的数据
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
public Node getNext() {
return this.next;
}
public String getData() {
return this.data;
}
// 实现节点的添加:
// 第一次调用（Link）：this代表Link.root
// 第二次调用（Node）：this代表Link.root.next
// 第三次调用（Node）：this代表Link.root.next.next
public void addNode(Node oldNode,Node newNode) {
System.out.println("now:"+oldNode);
if (this.next == null) { // 保存新节点
this.next = newNode;
} else { // 当前节点后面还有节点
this.next.addNode(this.next,newNode); // 当前节点的下一个节点继续保存,这里采用的是递归添加节点
}
System.out.println(oldNode+"=>"+this.next);
}
// 第一次调用（Link）：this代表Link.root
// 第二次调用（Node）：this代表Link.root.next
// 第三次调用（Node）：this代表Link.root.next.next
public void printNode() {
System.out.println("pp:"+this.data);// 输出当前数据
if (this.next != null) { // 如果还有下一个节点，输出下一节点
this.next.printNode(); // 递归打印节点，注意这里的this.next中的this指代
}
}
}
// 链表增加节点，输出节点数据
class Link {
private Node root; //新建根节点
public void add (String data){
Node newNode = new Node(data); //链表中新增节点类对象
if(this.root == null ){ // 如果链表还没有任何节点,就添加第一个节点作为根节点
this.root = newNode;
System.out.println("root:"+this.root);
}else{
System.out.println("new:"+newNode);
this.root.addNode(this.root,newNode); //从根节点节点新链接一个节点
}
}
//输出当前节点数据
public void print(){
if( this.root != null ){
this.root.printNode();
}
}
}
运行：
root:test.Node@7852e922
new:test.Node@4e25154f
now:test.Node@7852e922
test.Node@7852e922=>test.Node@4e25154f
new:test.Node@70dea4e
now:test.Node@7852e922
now:test.Node@4e25154f
test.Node@4e25154f=>test.Node@70dea4e
test.Node@7852e922=>test.Node@4e25154f
pp:hello
pp:world
pp:wwww
例子3:
关键是构造一个类，里面包含一个指向下一个元素的对象（指向下一个元素的指针）
public class LinkedList{
public static void main(String[] args){
MyLinkedList linkedList = new MyLinkedList();
System.out.println("-------start-------");
System.out.println("ll:"+linkedList.listEm());
for (int i=0;i<5;i++){ //新建链表
linkedList.add(i+1);
}
System.out.println("mm:"+linkedList.listEm()); //打印链表
for(int i=0;i<5;i++){ //删除链表
System.out.println("remove:"+linkedList.remove());
}
System.out.println("kk:"+linkedList.listEm());
System.out.println("-------end-------");
}
}
class Node<T> {
Node<T> next;
T element;
public Node( Node<T> next, T element){
this.next = next;
this.element = element;
}
}
class MyLinkedList<T> {
private int size ;
Node<T> last; //指向list中最后一个元素
Node<T> first; //指向list中第一个元素
Node<T> currRead; //指向当前读取的元素
// 默认构造函数
public MyLinkedList(){
this.size = 0;
this.last = new Node(null,-1);
this.first = last;
this.currRead = first;
}
//往链表中添加数据（队尾添加数据）
public void add(T element){
Node<T> newNode = new Node<T>(null,element);
this.last.next = newNode;
this.last = newNode; // 引用平移
if(size == 0){
this.first = newNode;
}
size ++;
}
//移除链表中的数据（队头移除）
public T remove(){
if(size == 0){
System.out.println("empty list ");
this.currRead = this.first;
return null;
}
T result = this.first.element;
this.first = this.first.next;
this.currRead = this.first;
size--;
return result;
}
//获取队列中的元素
public T get(){
if(this.currRead.next == null){
this.setReadAgain();
return this.currRead.element;
}
T result = this.currRead.element;
this.currRead = this.currRead.next;
return result;
}
//再次从头开始读取数据
public void setReadAgain() {
this.currRead = this.first;
}
public String listEm(){
StringBuilder sb = new StringBuilder();
for(int i=0;i<size;i++){
T ele = this.get();
sb.append(this.currRead.element + "-->");
}
return sb.toString();
}
//获取队列大小
public int getSize(){
return this.size;
}
}
运行：
-------start-------
ll:
mm:1-->2-->3-->4-->5-->
remove:1
remove:2
remove:3
remove:4
remove:5
kk:
-------end-------
例四：
public class LinkedList {
public static void main(String [] args){
Link l=new Link();
mytype[] la;
mytype dsome=new mytype("韩敏","dsome",21);
mytype shao=new mytype("邵晓","john",45);
mytype hua=new mytype("华晓风","jam",46);
mytype duo=new mytype("余小风","duo",1000);
mytype wang=new mytype("王秋","jack",21);
mytype shi=new mytype("韩寒","bob",3000);
mytype yu=new mytype("于冬","keven",30);
l.add(dsome);//测试增加节点
l.add(shao);
l.add(hua);
l.add(wang);
l.add(shi);
l.add(duo);
l.add(yu);
System.out.println("链表长度："+l.length());//链表长度
la=l.toArray();
for(int i=0;i<la.length;i++){
System.out.println(la[i].getInfo());
}
System.out.println("是否包含余小风:"+l.contains(duo)+"\n");
System.out.println("删除余小风后\n");
l.remove(duo);
la=l.toArray();
for(int i=0;i<la.length;i++){ //转化为数组之后输出
System.out.println(la[i].getInfo());
}
System.out.println("\n利用索引方法输出全部数据");
for(int i=0;i<l.length();i++){
System.out.println(l.get(i).getInfo());
}
System.out.println("是否包含余小风:"+l.contains(duo)+"\n");
l.clean();
System.out.println("执行清空操作后链表长度: "+l.length()+"\t是否为空链表："+l.isEmpty());
}
}
class Link {
//内部类
private class Node{
private Node next;
private mytype data;
public Node(mytype data){
this.data=data;
}
public void addNode(Node newNode){ //增加节点
if(this.next==null){
this.next=newNode; // 指向新的节点
}else{
this.next.addNode(newNode); // 递归调用是为了让next引用指向新的节点
}
}
public mytype getNode(int index){//按照角标返回数据
if(index==Link.this.foot++){
return this.data;
}else{
return this.next.getNode(index);
}
}
public boolean iscontain(mytype data){//判断是否含有该数据
if(this.data.equals(data)){
return true;
}else{
if(this.next!=null){
return this.next.iscontain(data);
}else{
return false;
}
}
}
public void removeNode(Node previous,mytype data){ //删除节点
if(this.data.equals(data)){ //this：下一个节点B
previous.next=this.next; // this.next:节点B的下一个节点C，previous：节点A
}else{
this.next.removeNode(this,data); //注意这里的this.next和this的区别：this.next是下一个节点B，this是当前节点A
}
}
public void toArrayNode(){ //转化数组
Link.this.Larray[Link.this.foot ++]=this.data; //每个节点的数据添加到一个mytype []中
if(this.next!=null){
this.next.toArrayNode();
}
}
}
//内部类定义完毕
private Node root;
private int count=0;
private int foot;
private mytype [] Larray;
public void add(mytype data){ //增加节点
if(data==null){
System.out.print("增加数据失败，数据为空");//测试用
return;
}
Node newNode=new Node(data); //新建节点
if(this.root==null){
this.root=newNode;
this.count++;
}else{
this.root.addNode(newNode);
this.count++;
}
}
public int length(){//链表长度
return this.count;
}
public boolean isEmpty(){//是否为空链表
if(this.count==0)return true;
else return false;
}
public void clean(){//清空链表
this.root=null;
this.count=0;
}
public mytype get(int index){//索引返回节点所存的数据
if(index>=this.count||index<0){
System.out.print("越界错误");//测试用
return null;
}else{
this.foot=0;
return this.root.getNode(index);
}
}
public boolean contains(mytype data){ //判断链表数据是否含data
if(data==null)
return false;
else
return this.root.iscontain(data);
}
public void remove(mytype data){ //删除指定数据节点
if(this.contains(data)){
if(this.root.data.equals(data)){
this.root=this.root.next;
this.count--;
}
else{
this.count--;
this.root.next.removeNode(root,data);
}
}else{
System.out.print("删除错误");//测试用
}
}
public mytype[] toArray(){ //把链表转化成对象数组
if(this.count==0){
return null;
}
this.foot=0;
this.Larray=new mytype [this.count];
this.root.toArrayNode();
return this.Larray;
}
}
class mytype {
private String name;
private String people;
private int age;
public mytype(String name,String people,int age){//链表中的数据（可自定义）
this.name=name;
this.people=people;
this.age=age;
}
public boolean equals(mytype data){//判断数据是否相同
if(this==data){
return true;
}
if(data==null){
return false;
}
if(this.name.equals(data.name)&&this.people.equals(data.people)&&this.age==data.age){
return true;
}else{
return false;
}
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getPeople() {
return people;
}
public void setPeople(String people) {
this.people = people;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getInfo(){
return "名字 :"+this.name+"\n"+
"人物 :"+this.people+"\n"+
"年龄 :"+this.age;
}
}
运行：
链表长度：7
名字 :韩敏
人物 :dsome
年龄 :21
名字 :邵晓
人物 :john
年龄 :45
名字 :华晓风
人物 :jam
年龄 :46
名字 :王秋
人物 :jack
年龄 :21
名字 :韩寒
人物 :bob
年龄 :3000
名字 :余小风
人物 :duo
年龄 :1000
名字 :于冬
人物 :keven
年龄 :30
是否包含余小风:true
删除多余后
名字 :韩敏
人物 :dsome
年龄 :21
名字 :邵晓
人物 :john
年龄 :45
名字 :华晓风
人物 :jam
年龄 :46
名字 :王秋
人物 :jack
年龄 :21
名字 :韩寒
人物 :bob
年龄 :3000
名字 :于冬
人物 :keven
年龄 :30
利用索引方法输出全部数据
名字 :韩敏
人物 :dsome
年龄 :21
名字 :邵晓
人物 :john
年龄 :45
名字 :华晓风
人物 :jam
年龄 :46
名字 :王秋
人物 :jack
年龄 :21
名字 :韩寒
人物 :bob
年龄 :3000
名字 :于冬
人物 :keven
年龄 :30
是否包含多余:false
执行清空操作后链表长度: 0 是否为空链表：true
参考：
https://blog.csdn.net/qq_37199582/article/details/79244657
https://blog.csdn.net/google_huchun/article/details/52824024
