链表的结构
线性结构的链式存储是用若干地址分散的存储单元存储数据元素,逻辑上相邻的两个数据元素在物理位置上并不一定相邻,必须采用附加信息来表示数据元素之间的顺序关系。因此存储一个数据元素的数据单元至少包含两部分------数据域和地址域 上述的结构通常称为结点 一个节点表示一个数据元素,通常节点当中的地址会把数据结点连接起来,节点当中的连接关系体现了线性表当中数据元素间的顺序关系,采用这种关系的称为线性链表。 从上图当中,head是线性链表当中的第一个节点,但是这个节点在数据域当中并没有存储数据,这里之所以写这个的目的是我们能够通过头指针去遍历我们整个链表。 最后一个节点的地址域为空,表示其后不再有节点。每个结点只有一个地址域的链表称为单链表
定义链表节点
public class ListNode {
int val;
ListNode next;
public ListNode(int value){
this.val = value;
}
@Override
public String toString() {
return "ListNode{" +
"val=" + val +
", next=" + next +
'}';
}
}
建立单链表
public class Test {
public static void main(String[] args) {
ListNode node1=new ListNode(1);
ListNode node2=new ListNode(2);
ListNode node3=new ListNode(3);
ListNode node4=new ListNode(4);
ListNode node5=new ListNode(5);
ListNode node6=new ListNode(6);
node1.next=node2;
node2.next=node3;
node3.next=node4;
node4.next=node5;
node5.next=node6;
node6.next=null;
System.out.println(node1);
LinkList linkList1=new LinkList();
linkList1.head=node1;
System.out.println("输出链表的值");
linkList1.printLink();
System.out.println("输出链表的长度");
System.out.println(linkList1.GetListLength());
System.out.println("查找某个元素是否在链表节点上");
System.out.println(linkList1.contains(3));;
linkList1.add(0,3);
System.out.println("指定位置插入节点");
linkList1.printLink();
linkList1.delete(1);
System.out.println("删除指定位置节点");
linkList1.printLink();
}
}
链表的创建和遍历(头插法和尾插法)
public class LinkList{
ListNode head=null;
public void headInsert(int val){
ListNode listNode = new ListNode(val);
if (head == null){
head = listNode;
return;
}
listNode.next = listNode;
head = listNode;
}
public void EndInsert(int val){
ListNode listNode = new ListNode(val);
if (head == null) {
head = listNode;
return;
}
ListNode indexNode = listNode;
while (indexNode != null){
indexNode=indexNode.next;
}
indexNode.next = listNode;
}
public void printLink(){
ListNode tempNode=head;
while (tempNode != null) {
System.out.println(tempNode.val);
tempNode = tempNode.next;
}
System.out.println();
}
public int GetListLength(){
ListNode tempNode = head;
int length=0;
while (tempNode != null) {
length++;
tempNode = tempNode.next;
}
return length;
}
}
}
链表中查找某节点
public boolean contains(int val){
ListNode tempNode = head;
int length = 0;
while (tempNode != null) {
if (tempNode.val == val) {
return true;
}
tempNode = tempNode.next;
}
return false;
}
指定位置插入节点
public void add(int val,int index){
if (index < 0 || index >= GetListLength()){
throw new IndexOutOfBoundsException("插入位置不合法");
}
if (index==0){
headInsert(val);
} else if (index==GetListLength()){
EndInsert(val);
}else {
ListNode listNode=new ListNode(val);
ListNode temp=head;
ListNode pre=null;
int position=0;
while (temp != null){
if (position==index){
listNode.next=temp;
pre.next=listNode;
return;
}
pre=temp;
temp=temp.next;
position++;
}
}
}
指定位置删除节点
public void delete(int index){
if (index<0&&index>GetListLength()){
throw new IndexOutOfBoundsException("删除位置不合法");
}
if (index==0){
head=head.next;
return;
}
ListNode temp=head;
ListNode pre=null;
int position=0;
while (temp != null){
if (position==index){
pre.next=temp.next;
temp.next=null;
return;
}
pre=temp;
temp=temp.next;
position++;
}
}
|