一、链表定义
链表通过指针将一组零散的内存块串联在一起进行使用。
数据格式：
根据上面的图展示，每个内存块可以称为链条的一个“结点”，结点包含了数据和下一个结点的地址；同时有2个结点特殊：第一个结点和最后一个结点，第一个结点称为“头节点”，存储链表基地址，最后一个结点称为“尾节点”，尾节点的下一个结点为空地址 NULL。
二、链表实现定义
public class LinkList<T> {
//结点定义
private class Node{
//数据
T item;
//指向下一个结点
Node next;
//构造器
public Node(T item,Node next){
this.item = item;
this.next = next;
}
public Node(T item){
this.item = item;
}
}
//头结点
private Node head;
//尾结点
private Node tail;
//结点个数
private int size;
//链表定义
public LinkList(){
this.head = new Node(null,null);
size = 0;
}
}
三、查找特定位置的链表结点
//查找特定位置的链表结点
public Node get(int index) {
if (index <0 || index >=this.size){
return null;
}else{
Node temp = this.head;
for(int i =1;i<=index;i++){
temp = temp.next;
}
return temp;
}
}
四、插入链表结点
注意：
将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。
//在链表的第i个位置插入一个值为t数据
public void insert(int index ,T data) throws Exception{
if(index <0 ||index > this.size){
throw new Exception("插入超出范围");
}else{
Node newNode = new Node(data);
//在头结点插入元素
if (index ==0){
if(this.size >0){
Node temp = head;
newNode.next = temp;
}
head = newNode;
}
//在尾结点插入元素
else if(index == this.size){
Node temp = tail;
temp.next = newNode;
this.tail = newNode;
}else{
//在中间插入元素
Node preNode = get(index-1);
Node nextNode = preNode.next;
newNode.next = nextNode;
preNode.next = newNode;
}
}
this.size ++;
if(size == 1){
tail = head;
}
}
五、删除链表结点
//删除特定位置的数据
public void del(int index )throws Exception{
if (index <0 ||index >=this.size){
throw new Exception("删除超出范围");
}else{
//删除头结点
if (index == 0){
Node temp = this.head.next;
this.head = temp;
}else if(index == this.size-1){ //删除尾结点
Node preNode = get(index -1);
this.tail = preNode;
preNode.next = null;
}else{
//删除中间结点
Node preNode = get(index -1);
Node nextNode = preNode.next.next;
preNode.next = nextNode;
}
}
this.size --;
}
六、整体代码
public class LinkList<T> {
//结点定义
private class Node{
//数据
T item;
//指向下一个结点
Node next;
//构造器
public Node(T item,Node next){
this.item = item;
this.next = next;
}
public Node(T item){
this.item = item;
}
}
//头结点
private Node head;
//尾结点
private Node tail;
//结点个数
private int size;
//链表定义
public LinkList(){
this.head = new Node(null,null);
size = 0;
}
//查找特定位置的链表结点
public Node get(int index) {
if (index <0 || index >=this.size){
return null;
}else{
Node temp = this.head;
for(int i =1;i<=index;i++){
temp = temp.next;
}
return temp;
}
}
public void add(T data){
Node temp = new Node(data);
//链表为空时
if (this.size == 0){
head = temp;
tail = head;
}else{
Node last = tail;
last.next = temp;
this.tail = temp;
}
this.size ++;
}
//在链表的第i个位置插入一个值为t数据
public void insert(int index ,T data) throws Exception{
if(index <0 ||index > this.size){
throw new Exception("插入超出范围");
}else{
Node newNode = new Node(data);
//在头结点插入元素
if (index ==0){
if(this.size >0){
Node temp = head;
newNode.next = temp;
}
head = newNode;
}
//在尾结点插入元素
else if(index == this.size){
Node temp = tail;
temp.next = newNode;
this.tail = newNode;
}else{
//在中间插入元素
Node preNode = get(index-1);
Node nextNode = preNode.next;
newNode.next = nextNode;
preNode.next = newNode;
}
}
this.size ++;
if(size == 1){
tail = head;
}
}
//删除特定位置的数据
public void del(int index )throws Exception{
if (index <0 ||index >=this.size){
throw new Exception("删除超出范围");
}else{
//删除头结点
if (index == 0){
Node temp = this.head.next;
this.head = temp;
}else if(index == this.size-1){ //删除尾结点
Node preNode = get(index -1);
this.tail = preNode;
preNode.next = null;
}else{
//删除中间结点
Node preNode = get(index -1);
Node nextNode = preNode.next.next;
preNode.next = nextNode;
}
}
this.size --;
}
//移除末尾元素,并返回对应数据
public T remove() throws Exception{
if (this.size ==0){
throw new Exception("链表为空，无法移除");
}
//只有一个元素，移除后为空
if (this.size == 1){
T data = this.head.item;
this.head = null;
this.tail = this.head;
this.size --;
return data;
}else{
Node preNode = get(this.size-2);
T data = this.tail.item;
preNode.next = null;
this.tail = preNode;
this.size --;
return data;
}
}
//删除特定元素的第一个位置
public boolean deleteData(T data){
boolean flag = false;
if(this.size == 0){
return flag;
}else{
Node curNode = this.head;
//元素位于第一个结点
if (curNode.item == data){
Node nextNode = curNode.next;
head = nextNode;
flag = true;
//当前列表只有一个结点
if (this.size ==1){
tail = head;
}
this.size --;
}else {
while (curNode != null) {
Node nextNode = curNode.next;
if (nextNode != null && nextNode.item == data) {
//删除元素为尾结点
if (nextNode.next ==null){
this.tail = curNode;
curNode.next = null;
}else{
//删除结点为中间结点
Node temp = curNode.next.next;
curNode.next = temp;
}
flag = true;
this.size --;
break;
}
curNode = curNode.next;
}
}
}
return flag;
}
public void printLinkList(){
if(this.size ==0){
System.out.println("链表为空");
}
else {
Node temp = head;
System.out.print("目前的列表，头结点：" + head.item + ",尾结点:" + tail.item + ",整体：");
while (temp != null) {
System.out.print(temp.item + ",");
temp = temp.next;
}
System.out.println();
}
}
public static void main(String args[]) throws Exception {
LinkList linkList = new LinkList();
linkList.add("2");
linkList.del(0);
linkList.printLinkList();
linkList.insert(0,"a");
System.out.println("删除的元素为："+linkList.remove());
linkList.insert(0,"2");
linkList.insert(1,"3");
linkList.add("3");
linkList.printLinkList();
linkList.del(1);
linkList.printLinkList();
linkList.insert(1,"1");
linkList.insert(0,"0");
linkList.insert(2,"0");
linkList.del(2);
linkList.printLinkList();
linkList.deleteData(3);
linkList.printLinkList();
}
}
更多推荐
java实现链表
发布评论