链表基础

模板留作参考

C++:

#include <stdio.h>
struct node{
    int data;
    //数据域
    struct node *nxt;
    //指针域
};
int n,x,need_del;
struct node *head=NULL;
void add_list_tail(struct node **head,struct node *new_one)
{
    new_one->data=x;
    new_one->nxt=*head;
    *head=new_one;
    return;
}//在 list 尾部插入
void add_list_head(struct node **head,struct node *new_one)
{
    struct node *real_head=*head;
    new_one->data=x;
    if(real_head)
    {
        while(real_head->nxt)
            real_head=real_head->nxt;
        real_head->nxt=new_one;
    }
    else
        *head=new_one;
    new_one->nxt=NULL;//记得 if 里面也要将 nxt 标记为 NULL
    return;
}//在 list 头部插入
void traversal()
{
    for(struct node *p=head;p;p=p->nxt)
        printf("%d\n",p->data);
    return;
}//从尾部遍历 list
int del(int x)
{
    struct node *cur,*pre;
    for(cur=head,pre=head;cur&&cur->data!=x;cur=cur->nxt)
        pre=cur;
    if(!cur)
        return -1;//-1 代表没找到
    if(pre==cur)
        head=cur->nxt;// 防止删除尾部节点后 traversal 时因 head 未更改导致 RE
    pre->nxt=cur->nxt;
    free(cur);
    return 0;//0 代表成功删除了节点并正常退出
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        struct node *new_one=(struct node*)malloc(sizeof(struct node));
        scanf("%d",&x);
        //add_list_head(&head,new_one);
        add_list_tail(&head,new_one);
        //list 以第一个 nxt 指向空指针的结构体节点为头部
    }
    scanf("%d",&need_del);
    del(need_del);
    traversal();
    return 0;
}

Java:

public class LinkedList<ElemType> {
    private Node<ElemType> head; // 头结点

    public LinkedList() {
        head = new Node<ElemType>(); // 头结点不存储数据
    }

    public int length() { // 返回链表长度
        int count = 0;
        for (Node<ElemType> p = head.nxt; p != null; p = p.nxt) {
            count ++;
        }
        return count;
    }

    public boolean empty() { // 判断链表是否为空
        return head.nxt == null;
    }

    public void clear() { // 清空链表
        while (!empty()) {
            delete(1);
        }
    }

    public void traverse() { // 遍历链表
        for (Node<ElemType> p = head.nxt; p != null; p = p.nxt) {
            System.out.println(p.data);
        }
    }

    private Node<ElemType> getElemPtr (int pos, int limLeft, int limRight) { // 获取指定位置的结点指针
        if (pos < limLeft || pos > limRight) {
            throw new IllegalArgumentException("Position is out of range!"); // 抛出异常
        } else {
            int count = 0;
            for (Node<ElemType> p = head; p != null; p = p.nxt) {
                if (count == pos) {
                    return p;
                } else {
                    count ++;
                }
            }
        }
        return null;
    }

    public ElemType getElem(int pos) { // 获取指定位置的元素
        try {
            Node<ElemType> p = getElemPtr(pos, 1, length());
            return p.data;
        } catch (IllegalArgumentException e) { // 捕获异常
            e.printStackTrace();
        }
        return null;
    }

    public boolean setElem(int pos, ElemType val) { // 设置指定位置的元素
        try {
            Node<ElemType> p = getElemPtr(pos, 1, length());
            p.data = val;
            return true;
        } catch (IllegalArgumentException e) { // 捕获异常 
            e.printStackTrace();
        }
        return false;
    }

    public boolean delete(int pos) { // 删除指定位置的元素
        try {
            Node<ElemType> back = getElemPtr(pos - 1, 1, length()); // 被删除结点的前驱结点
            Node<ElemType> pst = back.nxt;  // 被删除结点
            back.nxt = back.nxt.nxt; // 删除结点
            pst = null; // 释放内存
            return true;
        } catch (IllegalArgumentException e) { // 捕获异常
            e.printStackTrace();
        }
        return false;
    }

    public boolean insert(int pos, ElemType val) { // 在指定位置插入元素
        try {
            Node<ElemType> back = getElemPtr(pos, 0, length()); // 被插入结点的前驱结点
            back.nxt = new Node<ElemType>(back.nxt, val); // 插入结点
            return true; 
        } catch (IllegalArgumentException e) {  // 捕获异常
            e.printStackTrace(); 
            return false;
        }
    }
}

class Node<ElemType> { // 链表结点类
    public Node<ElemType> nxt = null;
    public ElemType data;

    public Node() {}

    public Node(Node<ElemType> next, ElemType data) {
        this.nxt = next;
        this.data = data;
    }
}