双向链表的基本操作
程序员文章站
2024-03-22 11:17:16
...
class ListNode{
ListNode pre;
int val;
ListNode next;
ListNode(int val){
this.val=val;
}
ListNode(ListNode pre,int val,ListNode next){
this.pre=pre;
this.val=val;
this.next=next;
}
}
public class Test {
static ListNode head;//头节点
static ListNode tail;//尾节点
static int size;//链表长度
/*
* 增加元素(尾部插入)
* */
public static void add(int val) {
ListNode node=new ListNode(tail,val,null);
if(head==null) {
head=node;
}else {
tail.next=node;
}
tail=node;
size++;
}
/*
* 删除元素
* */
public static boolean remove(int index) {
if(index<0||index>size-1)
return false;
ListNode tmp;
if(index<(size>>1)) {//index在链表前半段
tmp=head;
for(int i=0;i<index;i++) {
tmp=tmp.next;
}
}else {//index在链表后半段
tmp=tail;
for(int i=size-1;i>index;i--) {
tmp=tmp.pre;
}
}
ListNode preNode=tmp.pre;//前驱节点
ListNode nextNode=tmp.next;//后继节点
if(preNode==null) {//待删节点是头节点
head=nextNode;
}else {//待删节点有前驱节点
preNode.next=nextNode;
tmp.pre=null;
}
if(nextNode==null) {//待删节点是尾节点
tail=preNode;
}else {//待删节点有后继节点
nextNode.pre=preNode;
tmp.next=null;
}
size--;
return true;
}
/*
* 查找某一个索引位置的元素
* */
public static int get(int index) {
if(index<0||index>size-1)
return -1;
ListNode tmp;
if(index<(size>>1)) {//index在链表前半段
tmp=head;
for(int i=0;i<index;i++) {
tmp=tmp.next;
}
return tmp.val;
} else {//index在链表后半段
tmp=tail;
for(int i=size-1;i>index;i--) {
tmp=tmp.pre;
}
return tmp.val;
}
}
/*
* 修改某个元素的值
* */
public static void set(int index,int val) {
if(index<0||index>size-1)
return ;
if(index<(size>>1)) {
ListNode tmp=head;
for(int i=0;i<index;i++) {
tmp=tmp.next;
}
tmp.val=val;
}else {
ListNode tmp=tail;
for(int i=size-1;i>index;i--) {
tmp=tmp.pre;
}
tmp.val=val;
}
}
/*
* 某个位置插入一个节点
* */
public static boolean add(int index,int val) {
if(index<0||index>size-1)
return false;
ListNode node=new ListNode(val);
ListNode tmp;
if(index<(size>>1)) {
tmp=head;
for(int i=0;i<index;i++) {
tmp=tmp.next;
}
}else {
tmp=tail;
for(int i=size-1;i>index;i--) {
tmp=tmp.pre;
}
}
node.next=tmp;
tmp.pre.next=node;
node.pre=tmp.pre;
tmp.pre=node;
return true;
}
/*
* 打印链表
* */
public static void print() {
if(head==null)
return ;
ListNode tmp=head;
while(tmp!=null) {
System.out.print(tmp.val+" ");
tmp=tmp.next;
}
}
public static void main(String[] args) {
add(1);
add(2);
add(3);
add(4);
add(5);
System.out.println("链表长度:"+size);
System.out.println("打印链表");
print();
set(2,7);
System.out.println();
System.out.println("把index为2的元素设为7后打印链表");
print();
remove(1);
System.out.println();
System.out.println("删除index为1的元素后打印链表");
print();
System.out.println();
add(2,6);
System.out.println("在index为2的位置插入值为6的节点后打印链表");
print();
}
}
输出:
链表长度:5
打印链表
1 2 3 4 5
把index为2的元素设为7后打印链表
1 2 7 4 5
删除index为1的元素后打印链表
1 7 4 5
在index为2的位置插入值为6的节点后打印链表
1 7 6 4 5