【本文详细介绍了JAVA应用开发中的链表,欢迎读者朋友们阅读、转发和收藏!】
1 基本概念
链表是一种数据结构,和数组同级,有单链表和双链表之分。
单链表(单向链表):由两部分组成,数据域( Data )和结点域 (Node), 单链表就像是一条打了很多结的绳子,每一个绳结相当于一个结点,每个节结点间都有绳子连接,这样原理的实现是通过 Node 结点区的头指针 head 实现的,每个结点都有一个指针,每个节点指针的指向都是指向自身结点的下一个结点,最后一个结点的 head 指向为 null, 这样一来就连成了上述所说绳子一样的链,对单链表的操作只能从一端开始,如果需要查找链表中的某一个结点,则需要从头开始进行遍历。
双链表(双向链表):双链表和单链表相比,多了一个指向尾指针( tail ),双链表的每个结点都有一个头指针 head 和尾指针 tail, 双链表结点的首结点的 head 指向为 null , tail 指向下一个节点的 tail; 尾结点的 head 指向前一个结点的 head , tail 指向为 null ,是双向的关系;
比如, Java 中我们使用的 ArrayList ,其实现原理是数组。而 LinkedList 的实现原理就是链表了。链表在进行循环遍历时效率不高,但是插入和删除时优势明显。
由于双向链表存在增删数据复杂等原因,在实际应用中,较多的是对于单项链表的使用,下面对单向链表做一个介绍。
单向链表是一种线性表,实际上是由节点( Node )组成的,一个链表拥有不定数量的节点。其数据在内存中存储是不连续的,它存储的数据分散在内存中,每个结点只能也只有它能知道下一个结点的存储位置。由 N 各节点( Node )组成单向链表,每一个 Node 记录本 Node 的数据及下一个 Node 。向外暴露的只有一个头节点( Head ),我们对链表的所有操作,都是直接或者间接地通过其头节点来进行的。
下面简单介绍下单项链表的实现
public class MyLink {
Node head = null; // 头节点
/**
* 链表中的节点,data代表节点的值,next是指向下一个节点的引用
*/
class Node {
Node next = null;// 节点的引用,指向下一个节点
int data;// 节点的对象,即内容
public Node(int data) {
this.data = data;
}
}
/**
* 向链表中插入数据
* @param d
*/
public void addNode(int d) {
Node newNode = new Node(d);// 实例化一个节点
if (head == null) {
head = newNode;
return;
}
Node tmp = head;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = newNode;
}
/**
*
* @param index:删除第index个节点
* @return
*/
public boolean deleteNode(int index) {
if (index < 1 || index > length()) {
return false;
}
if (index == 1) {
head = head.next;
return true;
}
int i = 1;
Node preNode = head;
Node curNode = preNode.next;
while (curNode != null) {
if (i == index) {
preNode.next = curNode.next;
return true;
}
preNode = curNode;
curNode = curNode.next;
i++;
}
return false;
}
/**
*
* @return 返回节点长度
*/
public int length() {
int length = 0;
Node tmp = head;
while (tmp != null) {
length++;
tmp = tmp.next;
}
return length;
}
/**
* 在不知道头指针的情况下删除指定节点
*
*/
public boolean deleteNode11(Node n) {
if (n == null || n.next == null)
return false;
int tmp = n.data;
n.data = n.next.data;
n.next.data = tmp;
n.next = n.next.next;
System.out.println("删除成功!");
return true;
}
public void printList() {
Node tmp = head;
while (tmp != null) {
System.out.println(tmp.data);
tmp = tmp.next;
}
}
public static void main(String[] args) {
MyLink list = new MyLink();
list.addNode(5);
list.addNode(3);
list.addNode(1);
list.addNode(2);
list.addNode(55);
list.addNode(36);
System.out.println("linkLength:" + list.length());
System.out.println("head.data:" + list.head.data);
list.printList();
list.deleteNode(4);
System.out.println("After deleteNode(4):");
list.printList();
}
}
领取专属 10元无门槛券
私享最新 技术干货