今天也是算法通关村刚开始,学习了链表。
首先,链表是一种最基本的结构,我们通常在收到一个链表的时候只有一个指向链表头的指针head,因为链表就是通过头指针来寻找其他结点的。
链表中的每个结点都存在它的数据和指向下一个节点的指针。
在遍历链表中,我们只需要在while循环中让它一直next就可以了,代码如下。
public static int getLength(Node head) {
int length = 0;
Node node = head;
while (node != null) {
length++;
node = node.next;
}
return length;
}
在插入链表时,三种情况,表头插入,中间插入,结尾插入。
1. 表头插入,由于我们是通过头指针来寻找其他结点的,所以我们只需要将头结点改为新结点就可以了,head = nodeInsert;
2. 中间插入,我们需要在目标节点的前一个位置停下来,这里定义为cur,需要让cur.next=新结点,再让new.next=cur.next,这样就让cur结点的下一个结点是新结点,新结点下一个结点为原来cur.next,这样就实现了插入;
3.结尾插入,只要将尾结点指向新结点就可以了。
public static Node insertNode(Node head, Node nodeInsert, int position) {
// 需要判空,否则后面可能会有空指针异常
if (head == null) {
return nodeInsert;
}
//越界判断
int size = getLength(head);
if (position > size + 1 || position < 1) {
System.out.println("位置参数越界");
return head;
}
//在链表开头插入
if (position == 1) {
nodeInsert.next = head;
//return nodeInsert;
//上面return还可以这么写:
head = nodeInsert;
return head;
}
Node pNode = head;
int count = 1;
while (count < position - 1) {
pNode = pNode.next;
count++;
}
nodeInsert.next = pNode.next;
pNode.next = nodeInsert;
return head;
}
链表删除,同样是三种情况,考虑表头,中间,表尾
1. 删除表头结点,只要执行head=head.next就行了
2. 删除中间结点,找到位置后,将cur.next指针的值更新为cur.next.next就可以解决
3. 删除表尾结点,只需要让表尾结点的前驱节点的next=null就可以了
public static Node deleteNode(Node head, int position) {
if (head == null) {
return null;
}
int size = getLength(head);
if (position > size || position <= 0) {
System.out.println("输入的参数有误");
return head;
}
if (position == 1) {
// head.next就是链表的新head
return head.next;
}
Node preNode = head;
int count = 1;
while (count < position) {
preNode = preNode.next;
count++;
Node curNode = preNode.next;
preNode.next = curNode.next;
}
return head;
}
其实,我觉得链表就是通过表头就可以想查哪个结点就查哪个结点,不管是要对链表中的结点增删改查,都需要通过头结点来next。
双向链表
每个结点都是有数据域,指向前一个结点的指针,指向后一个结点的指针,这样的话移动元素会更方便。但是相对来说,代码也就更多了,更复杂,但是道理都是一样的。文章来源:https://www.toymoban.com/news/detail-610409.html
在链表中间插入的时候,这里定义cur为要插入结点位置的前一个结点,需要先将当前结点的下一个结点的前一个结点等于新加入的结点,再让新结点的下一个结点设为现在cur的下一个结点,这样就完成了第一步,让新结点和要插入位置后边的结点联系起来了,然后让cur的下一个结点设为新插入的节点,再让当前节点的前一个结点设为cur,这样就让新加入的节点和cur结点联系起来了。关键代码为:文章来源地址https://www.toymoban.com/news/detail-610409.html
//某个结点的后部插入
public void insertAfter(int key, int data) {
DoubleNode newDoubleNode = new DoubleNode(data);
DoubleNode current = first;
while ((current != null) && (current.data != key)) {
current = current.next;
}
//若当前结点current为空
if (current == null) {
//current为null有两种情况 一种是链表为空,一种是找不到key值
if (isEmpty()) { //1、链表为空
//则插入第一个结点(其实可以调用其它的Insert方法)
first = newDoubleNode;
//first和last均指向该结点(第一个结点)
last = newDoubleNode;
} else {
//2、找不到key值
last.next = newDoubleNode;
newDoubleNode.prev = last; //则在链表尾部插入一个新的结点
last = newDoubleNode;
}
} else { //第三种情况,找到了key值,分两种情况
if (current == last) {
//1、key值与最后结点的data相等
newDoubleNode.next = null;
//由于newNode将是最后一个结点,则将last指向newNode
last = newDoubleNode;
} else {
//2、两结点中间插入
newDoubleNode.next = current.next;
current.next.prev = newDoubleNode;
}
current.next = newDoubleNode; //将当前结点的next域指向newNode
newDoubleNode.prev = current; //将新结点的previous域指向current
}
}
到了这里,关于编程导航算法第一关 |链表的基础的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!